力扣题解198.打家劫舍


思路都在注释

自己写的

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 1) return nums[0];
        if (nums.size() == 2) return max(nums[0], nums[1]);    
        //dp[i]:表示偷到第i家人的最大金额   
        int dp[(int)nums.size()]; 
        memset(dp, 0, sizeof(dp)); //数组初始化
        dp[0] = nums[0], dp[1] = max(nums[0], nums[1]); //边界初始化
        for (int i = 2; i < nums.size(); i++) {
            // dp[i - 1]:表示不偷
            // 偷到第i家人,有两种情况:
            // 1、偷之后dp[i] = nums[i] + dp[i - 2],
            // 2、不偷之后dp[i] = dp[i - 1]
            dp[i] = max(nums[i] + dp[i - 2], dp[i - 1]); // 状态定义
        }
        return dp[(int)nums.size() - 1];
    }
};

简化版

class Solution {
public:
    int rob(vector<int>& nums) {
        vector <int> dp(nums.size() + 1, 0); 
        dp[1] = nums[0]; 
        for (int i = 1; i < nums.size(); i++) {
            dp[i + 1] = max(dp[i], dp[i - 1] + nums[i]);
        }
        return dp[nums.size()];
    }
};

文章作者: Axieyun
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Axieyun !
评论
评论
  目录