题目描述1

代码

c++
java
python
#include <iostream>
#include <vector>

using namespace std;

int rob(vector<int>& nums) {
    if (nums.size() == 0) {
        return 0;
    }
    int N = nums.size();
    vector<int> dp(N + 1, 0);
    dp[0] = 0;
    dp[1] = nums[0];
    for (int k = 2; k <= N; k++) {
        // 偷前 k - 1 间房间的最大金额 或者 偷前 k - 2 间房间和最后一间的最大金额.
        dp[k] = max(dp[k - 1], nums[k - 1] + dp[k - 2]);
    }
    return dp[N];
}

int main(int argc, char* argv[]) {
    vector<int> nums = {2, 7, 9, 3, 1};
    int result = rob(nums);
    cout << result << endl;
}

class Solution:
    def rob(self, nums: list[int]) -> int:
        n = len(nums)
        f = [0] * (n+2)
        # enumerate 用于将一个可迭代对象(如列表、元组、字符串等)转换为一个枚举对象，可以同时获取元素的索引和值.
        # enumerate 函数返回一个枚举对象，其中每个元素是一个包含索引和值的元组.
        for i, x in enumerate(nums):
            # 由 f[i] = max(f[i-1], f[i-2]+nums[i]) ====> f[i+2] = max(f[i+1], f[i]+nums[i+2])
            f[i+2] = max(f[i+1], f[i] + x)
        # 由 return f[n-1] ====> return f[n+1]
        return f[n+1]

if __name__ == "__main__":
    s = Solution()
    my_list = [2,7,9,3,1]
    result = s.rob(my_list)
    print(result)

视频链接

+ 视频

打家劫舍

+ 在线测试

链接

  1. 动态规划

链接

  1. 打家劫舍https://leetcode.cn/problems/house-robber/description/ ↩︎