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];
}
};
在解给出想起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
),我认为这是比较容易理解窃取的最高金额。
如果我理解正确,您的问题可简化为: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(钱少)。
大部分社区成员都在享受秋假,或者我的问题的可见性受到限制。我不确定哪一个是真的。我多么想念人们过去常常回答(或投票)问题的时间! –
把'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,是的,你确实比我的更有意义!谢谢! –