Interview Classic 150 Questions P198 House Robber

---

Timeline

Timeline

2025-12-12

init

Dynamic Programming

---

Problem:

P198 House Robber

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

Dynamic programming, let dp[i][0] be the maximum value when not choosing nums[i], and dp[i][1] be the maximum value when choosing nums[i], then we have:

$$dp[i][0] = max(dp[i-1][0], dp[i-1][1]);$$

$$dp[i][1] = dp[i-1][0] + nums[i];$$

#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));
                // Not choose nums[i], choose 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);
}

leetcode hot 100 rewrite

#include <vector>
using std::vector;

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

                // vector<int> dp(n);
                // dp[i][0] represents the maximum amount when not robbing i
                // dp[i][1] represents the maximum amount when robbing i
                // dp[i][0] = max{dp[i-1][0], dp[i-1][1]}
                // dp[i][1] = dp[i-1][0] + nums[i]

                vector<vector<int> > dp(n, vector<int>(2));
                dp[0][0] = 0;
                dp[0][1] = nums[i];
                for (i = 1; i < n; i++) {
                        dp[i][0] = std::max(dp[i - 1][0], dp[i - 1][1]);
                        dp[i][1] = dp[i - 1][0] + nums[i];
                }
                return std::max(dp[n - 1][0], dp[n - 1][1]);
        }
};