时间轴

2025-12-12

init

题目：

P198 打家劫舍

https://leetcode.cn/problems/house-robber/description/?envType=study-plan-v2&envId=top-interview-150

动态规划，记dp[i][0]表示不选择nums[i]的最大值，dp[i][1]表示选择nums[i]的最大值，那么有：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <vector>
using std::vector;

class Solution {
    public:
        int rob(vector<int> &nums)
        {
                int i, n = nums.size();

                if (n == 1) {
                        return nums[0];
                }
                vector<vector<int> > dp(n, vector<int>(2, 0));
                // 不选择nums[i]，选择nums[i]
                dp[0] = { 0, nums[0] };
                for (i = 1; i < n; i++) {
                        dp[i][0] = std::max(dp[i - 1][1],
                                            dp[i - 1][0]);
                        dp[i][1] = dp[i - 1][0] + nums[i];
                }
                return std::max(dp[n-1][0], dp[n-1][1]);
        }
};
int main(){
        Solution S;
        vector<int> nums = {1,2,3,1};
        S.rob(nums);
}