Grund für eine solche Initialisierung von DP-Array

Question

Ich lösen a question von LeetCode.com. Die Frage ist so:

Sie sind ein professioneller Räuber, der plant, Häuser entlang einer Straße zu berauben. Jedes Haus hat eine bestimmte Menge Geld versteckt, die einzige Einschränkung, die Sie daran hindert, jeden von ihnen zu berauben, ist, dass benachbarte Häuser mit einem Sicherheitssystem verbunden sind und automatisch die Polizei kontaktieren, wenn in derselben Nacht zwei benachbarte Häuser einbrechen.
Geben Sie eine Liste der nicht negativen ganzen Zahlen an, die die Geldsumme jedes Hauses darstellen, und bestimmen Sie die maximale Menge an Geld, die Sie heute Nacht ausrauben können, ohne die Polizei zu alarmieren.

Nachdem er eine Weile darüber nachgedacht, ich mit der folgenden Beziehung kommen könnte, was richtig ist: Jedoch

dp[i] = max(dp[i-2]+nums[i], dp[i-1]); 

konnte ich die dp[] Array nicht initialisiert werden. In den Lösungen wurde es wie folgt initialisiert:

dp[0]=nums[0]; 
dp[1]=max(nums[0],nums[1]); 

Ist das nicht falsch? Denn wenn nums[0]>nums[1], dann bedeutet es nicht, das gleiche Haus zu berauben (weil wir sowohl dp[0] als auch dp[1] auf den gleichen Wert initialisieren?) Selbst wenn wir davon ausgehen, dass nums[1]>nums[0], nums[0] und nums[1] nicht aufeinanderfolgende Häuser sind?

Voll Code (falls erforderlich) unter:

class Solution { 
public: 
    int rob(vector<int>& nums) { 
     if(nums.empty()) 
      return 0; 

     vector<int> dp(nums.size()); 
     dp[0]=nums[0]; 
     dp[1]=max(nums[0], nums[1]); 

     for(int i=2; i<nums.size(); i++) { 
      dp[i] = max(nums[i]+dp[i-2], dp[i-1]); 
     } 

     return dp[nums.size()-1]; 
    } 
}; 

Answer 1

In der Lösung gegeben denken an dp[i] als „die maximale Menge an Geld, können Sie rauben aus i+1 Häuser ohne die Polizei zu alarmiert“ und betrachten jeweils i als separater Fall. Wenn es 1 Haus gibt (i == 0), dann kannst du nur von diesem Haus stehlen. Wenn es zwei Häuser gibt (i == 1), dann ist das Maximum, das Sie stehlen können, das Maximum von jedem Haus (nums[0] oder nums[1]). So wie ich es tat, war:

int n = nums.size(); 
int dp[n+1]; // max $ you can rob from i houses with altering police 
dp[0] = 0; // no houses, no money 
dp[1] = nums[0]; 
for (int i = 2; i <= n; ++i) { 
    dp[i] = max(dp[i - 1], nums[i - 1] + dp[i - 2]); 
} 
return dp[n]; 

, die die maximale Menge an Geld bringt Sie von i Häuser (nicht i+1) stehlen kann, was ich denke, ist leichter zu verstehen.

Answer 2

Wenn ich richtig verstehe, reduziert sich Ihre Frage auf: Because if nums[0]>nums[1], then doesn't it imply robbing the same house (because we initialize both dp[0] and dp[1] to the same value?).

Die Antwort ist nein, es bedeutet nicht, das gleiche Haus auszurauben. es bedeutet nicht, das Haus 1 zu berauben, weil Haus 0 ausgeraubt wurde. Und Haus 0 wurde ausgeraubt, weil es mehr Geld enthielt und man sich entscheiden musste, entweder Haus 0 oder Haus 1 (das weniger Geld hatte) zu rauben.