DP陣列初始化的原因

我正在從LeetCode.com上解決a question。問題是這樣的：DP陣列初始化的原因

你是一個專業的搶劫者計劃搶劫沿街的房屋。每間房屋都藏有一定數量的金錢，唯一阻止你搶劫每間房屋的限制因素是鄰近的房屋有保安系統連接，並且如果在同一晚上有兩間相鄰的房屋被闖入，它將自動與警方聯繫。
給出一個代表每個房屋的金額的非負整數列表，確定你可以在沒有提醒警方的情況下搶劫的最高金額。

思考了一段時間後，我能想出下面的關係，這是正確的：

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

但是，我不能初始化dp[]陣列。在解決方案中，它已被初始化爲這樣：

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

這不正確嗎？因爲如果nums[0]>nums[1]，那麼這是不是意味着搶劫同一棟房子（因爲我們初始化了dp[0]和dp[1]到相同的值？）即使我們假設nums[1]>nums[0]，nums[0]和nums[1]是不是連續的房子？

的完整代碼（如果需要）低於：

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]; 
    } 
};

來源

2017-10-08 Umedh Singh Bundela

大部分社區成員都在享受秋假，或者我的問題的可見性受到限制。我不確定哪一個是真的。我多麼想念人們過去常常回答（或投票）問題的時間！ –

把'dp [i]'想象成：「你可以從'i + 1'房屋中搶劫而不必警覺警察的最大金額」，並將每個'i'視爲一個單獨的案例。如果有一間房子（'i == 0'），那麼你只能從那間房子偷走。如果有兩間房子（'i == 1'），那麼你可以偷的最多的是來自任何房子的最大值（'nums [0]或nums [1]'）。我這樣做的方式是'int dp [i + 1]; dp [0] = 0; dp [1] = nums [1]; ... return dp [nums.size（）]'我認爲這更直觀。 – 0x499602D2

@ 0x499602D2，是的，你確實比我的更有意義！謝謝！ –

在解給出想起dp[i]爲「錢，你可以搶從i+1住房的最高限額不驚動警察」，並期待在作爲一個單獨的案例，每個i。如果有1間房屋（i == 0），那麼你只能從那間房屋偷竊。如果有兩棟房屋（i == 1），那麼你可以偷的最多的是兩棟房屋中的最大值（nums[0]或nums[1]）。我所採取的方式是：

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];

返回你可以從i房屋（不i+1），我認爲這是比較容易理解竊取的最高金額。

來源

2017-10-08 21:59:36 0x499602D2

如果我理解正確，您的問題可簡化爲：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?)。

答案是否定的，並不意味着搶劫同一棟房屋。這意味着不會搶劫房屋1，因爲房屋0被搶劫。而房屋0被搶劫，因爲它包含更多的錢，你必須選擇搶劫房屋0還是房屋1（錢少）。

來源

2017-10-09 07:18:27 fjardon

DP陣列初始化的原因

回答

相關問題