Week3-Day5 | #秒懂本题DP思路#

举个例子来算一下如何取最优

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