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阵列初始化的原因

回答

相关问题