举个例子来算一下如何取最优
[1 3 4 6]
我们从开始选择,此时能够得到的最大值是1,
到时,我们应该在
中选择,最大值变为3,
此时到,此时选择是从前一个的最大值和
+下标为2-2时的最大值来比较取最大值,
到时,应该从前一个的最大值和
+下标为3-2时的最大值,及
我们创建f数组,f[i]表示前i个房子能够得到的最大值
那么就可以替换一下上面的分析
f[0]=nums[0]
f[1]=max(nums[0],nums[1])
f[2]=max(f[2-1],nums[2]+f[2-2])
f[3]=max(f[3-1],nums[3]+f[3-1])
那么可以得出状态转移方程
code
#include <vector>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int rob(vector<int>& nums) {
int n=nums.size();
if(n==1)return nums[0];
vector<int>f(n);
f[0]=nums[0];
f[1]=max(nums[0],nums[1]);
for(int i=2;i<n;i++){
f[i] = max(f[i-1],nums[i]+f[i-2]);
}
return f[n-1];
}
};