DP状态机和DP数组解决打家劫舍

打家劫舍问题：
问：为什么只需要考虑从左往右（从右往左）偷？我就不能从中间开始偷吗？

答：先偷 A 再偷 B，先偷 B 再偷 A，都是一样的，因为我们只关心最终能偷多少钱。推广，任意一种偷房子的顺序，都可以重新排列成从左到右（从右往左）偷。
先看灵神的思路：
一、递归搜索 + 保存计算结果 = 记忆化搜索
这个cache装饰器就是我之前那个需要一个memo的字典在py里面，把索引key对应的value保存，否则就return对应的值，或者用C的方式就是拿一个容量大的memo数组，里面每个索引对应的值都为-1，然后每当记忆的时候就保存改变-1成对应的值，之后return，还是不如DP数组方便

class Solution:
    def rob(self, nums: List[int]) -> int:
        # dfs(i) 表示从 nums[0] 到 nums[i] 最多能偷多少
        @cache  # 缓存装饰器，避免重复计算 dfs 的结果
        def dfs(i: int) -> int:
            if i < 0:  # 递归边界（没有房子）
                return 0
            return max(dfs(i - 1), dfs(i - 2) + nums[i])

        return dfs(len(nums) - 1)  # 从最后一个房子开始思考

复杂度分析
时间复杂度：O(n)，其中 n 是 nums 的长度。
空间复杂度：O(n)。
二、1:1 翻译成递推
直接翻译的话，dfs(i) 翻译成 f[i]。

但记忆化搜索会访问 dfs(−2) 和 dfs(−1)，f[−2] 和 f[−1] 下标越界了。

解决办法：在 f 数组的前面插入两个 0，把 f 数组整体往右偏移 2 位。偏移后，dfs(i) 翻译成 f[i+2]。
这样避免了下标是负数的问题
注意只有 f 发生了偏移，nums 并没有偏移。

class Solution:
    def rob(self, nums: List[int]) -> int:
        f = [0] * (len(nums) + 2)
        for i, x in enumerate(nums):
            f[i + 2] = max(f[i + 1], f[i] + x)
        return f[-1]

复杂度分析
时间复杂度：O(n)。其中 n 是 nums 的长度。
空间复杂度：O(n)。
三、空间优化

class Solution:
    def rob(self, nums: List[int]) -> int:
        f0 = f1 = 0
        for x in nums:
            f0, f1 = f1, max(f1, f0 + x)
        return f1

复杂度分析
时间复杂度：O(n)。其中 n 是 nums 的长度。
空间复杂度：O(1)。
下面按C语言 我们做一下习题总结一下

一、198 打家劫舍：最大值 DP
二、494 目标和：方案数 DP / 01背包计数

一、198 打家劫舍

1. 前提条件

题目给一个数组：

int* nums;
int numsSize;

nums[i] 表示第 i 个房子的钱。

规则：不能偷相邻两个房子。

目标：求最多能偷多少钱。

LeetCode 198 的题意就是在不触发相邻房屋警报的情况下，求最大偷窃金额。

2. 先想递归

定义：dfs(i)

表示：从第 i 个房子开始偷，最多能偷多少钱。

对于第 i 个房子，有两个选择。

选择一：偷第 i 个

偷了第 i 个，就不能偷 i + 1。

所以收益是：nums[i] + dfs(i + 2)
选择二：不偷第 i 个

直接看下一个：dfs(i + 1)

所以：

$$dfs(i) = max(nums[i] + dfs(i + 2), dfs(i + 1))$$

3.加 memo：记忆化搜索

#include <stdlib.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int dfs(int* nums, int numsSize, int i, int* memo) {
    if (i >= numsSize) {
        return 0;
    }

    if (memo[i] != -1) {
        return memo[i];
    }

    int rob = nums[i] + dfs(nums, numsSize, i + 2, memo);
    int notRob = dfs(nums, numsSize, i + 1, memo);
//这里是把打劫的就是从最左边开始计算，打劫就跳到i+2个，然后memo保存，不打劫就i+1，因为只是说不能相邻，所以就是memo每次保存从第i个房子获得的最大收益
    memo[i] = max(rob, notRob);

    return memo[i];
}

int rob(int* nums, int numsSize) {
    int* memo = malloc(numsSize * sizeof(int));

    for (int i = 0; i < numsSize; i++) {
        memo[i] = -1;
    }
//这里是分配空间，最后把return出来的memo[i]作为ans
    int ans = dfs(nums, numsSize, 0, memo);

    free(memo);

    return ans;
}

这就是：递归 + 缓存 = 记忆化搜索 = 自顶向下 DP
5. 改成 DP 数组

递归里：dfs(i) = max(nums[i] + dfs(i + 2), dfs(i + 1))

换成 DP：dp[i] = max(nums[i] + dp[i + 2], dp[i + 1])

这里：dp[i] 表示从第 i 个房子开始，最多能偷多少钱。

因为 dp[i] 依赖后面的 dp[i + 1] 和 dp[i + 2]，所以要从后往前算。

6. DP 数组 C 代码

#include <stdlib.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int rob(int* nums, int numsSize) {
    int* dp = malloc((numsSize + 2) * sizeof(int));

    for (int i = 0; i < numsSize + 2; i++) {
        dp[i] = 0;
    }

    for (int i = numsSize - 1; i >= 0; i--) {
        int rob = nums[i] + dp[i + 2];
        int notRob = dp[i + 1];
//把倒着每次算出来的结果最大收益保存在dp数组里面
        dp[i] = max(rob, notRob);
    }

    int ans = dp[0];

    free(dp);

    return ans;
}

7. 另一种常见定义

也可以定义：dp[i] 表示偷到第 i 个房子为止，最多能偷多少钱。

转移：

$$dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])$$

这个也是最常见的写法；很多题解按这个方向写。
也就是从前往后算
C 代码：

#include <stdlib.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int rob(int* nums, int numsSize) {
    if (numsSize == 0) {
        return 0;
    }

    if (numsSize == 1) {
        return nums[0];
    }

    int* dp = malloc(numsSize * sizeof(int));

    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);

    for (int i = 2; i < numsSize; i++) {
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
    }

    int ans = dp[numsSize - 1];

    free(dp);

    return ans;
}

8. 空间优化

因为：dp[i] 只依赖 dp[i - 1] 和 dp[i - 2]

所以不用整个数组。

int max(int a, int b) {
    return a > b ? a : b;
}

int rob(int* nums, int numsSize) {
    int prev2 = 0;
    int prev1 = 0;

    for (int i = 0; i < numsSize; i++) {
        int cur = max(prev1, prev2 + nums[i]);

        prev2 = prev1;
        prev1 = cur;
    }

    return prev1;
}

含义：

prev2 = dp[i - 2]
prev1 = dp[i - 1]
cur = dp[i]
9. 易错点
易错点 1：偷了当前房子，不能偷下一个

所以不是：nums[i] + dfs(i + 1)

而是：nums[i] + dfs(i + 2)

易错点 2：最大值问题用 max

打家劫舍问的是：最多多少钱

所以转移里是：

max(...)

不是加起来。

易错点 3：DP 定义不同，遍历方向不同

如果定义：dp[i] = 从第 i 个房子开始偷

就从后往前算。

如果定义：dp[i] = 偷到第 i 个房子为止

就从前往后算。

10. 题型总结
    198 打家劫舍：

题型：
线性 DP / 最大值 DP

核心决策：
偷当前房子
不偷当前房子

递归：

$$dfs(i) = max(nums[i] + dfs(i + 2), dfs(i + 1))$$

DP：

$$dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])$$

空间优化：
只保留前两个状态。

一句话：

打家劫舍的本质是：每个位置都在“偷”和“不偷”之间做最大收益选择。
二、494 目标和

1. 前提条件

题目给：

int* nums;
int numsSize;
int target;

每个数前面可以加：

要求：

最终表达式等于 target 的方案数。

LeetCode 494 的题意是：给数组中每个整数前添加 + 或 -，构造表达式，使结果等于 target，返回方案数。

2. 先想递归

定义：

dfs(i, sum)

表示：

处理到第 i 个数时，当前和是 sum，最后能凑成 target 的方案数。

对于 nums[i] 有两个选择。

选择一：加 +
dfs(i + 1, sum + nums[i])
选择二：加 -
dfs(i + 1, sum - nums[i])

所以：

dfs(i, sum)
= dfs(i + 1, sum + nums[i])

• dfs(i + 1, sum - nums[i])

为什么是加？

因为题目问：

有多少种方案

所以左右两种选择的方案数要加起来。

3. 暴力递归 C 代码

int dfs(int* nums, int numsSize, int target, int i, int sum) {
    if (i == numsSize) {
        if (sum == target) {
            return 1;
        } else {
            return 0;
        }
    }

    int add = dfs(nums, numsSize, target, i + 1, sum + nums[i]);
    int sub = dfs(nums, numsSize, target, i + 1, sum - nums[i]);

    return add + sub;
}

int findTargetSumWays(int* nums, int numsSize, int target) {
    return dfs(nums, numsSize, target, 0, 0);
}

这个思路直观，但会超时。

因为很多：

dfs(i, sum)

会重复出现。

4. 记忆化搜索：处理负数 sum

问题是：

sum 可能是负数，不能直接当数组下标。

所以要加一个偏移量。

设：

$$total = nums 所有元素之和$$

那么 sum 的范围是：

$$[-total, total]$$

可以用：

sum + total

把负数下标平移成非负数。

例如：

$$sum = -3$$ $$total = 10$$ $$index = sum + total = 7$$

5. 记忆化搜索 C 代码

这里用二维数组：

memo[i][sum + total]

表示：

处理到 i，当前和为 sum 时的方案数。

#include <stdlib.h>

int dfs(int* nums, int numsSize, int target, int i, int sum,
        int total, int** memo) {
    if (i == numsSize) {
        if (sum == target) {
            return 1;
        } else {
            return 0;
        }
    }

    int index = sum + total;

    if (memo[i][index] != -1) {
        return memo[i][index];
    }

    int add = dfs(nums, numsSize, target, i + 1, sum + nums[i], total, memo);
    int sub = dfs(nums, numsSize, target, i + 1, sum - nums[i], total, memo);

    memo[i][index] = add + sub;

    return memo[i][index];
}

int findTargetSumWays(int* nums, int numsSize, int target) {
    int total = 0;

    for (int i = 0; i < numsSize; i++) {
        total += nums[i];
    }

    if (target > total || target < -total) {
        return 0;
    }

    int cols = 2 * total + 1;

    int** memo = malloc(numsSize * sizeof(int*));

    for (int i = 0; i < numsSize; i++) {
        memo[i] = malloc(cols * sizeof(int));

        for (int j = 0; j < cols; j++) {
            memo[i][j] = -1;
        }
    }

    int ans = dfs(nums, numsSize, target, 0, 0, total, memo);

    for (int i = 0; i < numsSize; i++) {
        free(memo[i]);
    }

    free(memo);

    return ans;
}

6. 转成 01 背包

目标和这题还有一个更常用、更重要的 DP 转换。

把加 + 的数看成一组，和为 positive。

把加 - 的数看成一组，和为 negative。

有：

$$positive - negative = target$$ $$positive + negative = total$$

两式相加：

$$2 * positive = target + total$$

所以：

$$positive = (target + total) / 2$$

于是问题变成：

从 nums 中选一些数，使它们的和为 positive，有多少种选法。

这就是 01 背包的“方案数”问题；很多题解也会这样把目标和转换成背包计数问题。

7. 什么情况下无解？

$$positive = (target + total) / 2$$

必须是整数。

所以如果：

target + total 是奇数

无解。

另外如果：

target > total 或 target < -total

也无解。

8. 01 背包 DP 状态定义

定义：

dp[j]

表示：

凑出和为 j 的方案数。

初始化：

$$dp[0] = 1$$

意思是：

什么都不选，凑出 0，有 1 种方案。
9. 状态转移

对于每个数 x = nums[i]：

选 x：

$$dp[j] += dp[j - x]$$

也就是：

$$dp[j] = dp[j] + dp[j - x];$$

注意 j 要倒序遍历。

因为每个数只能用一次。

10. 01 背包 C 代码

#include <stdlib.h>

int findTargetSumWays(int* nums, int numsSize, int target) {
    int total = 0;

    for (int i = 0; i < numsSize; i++) {
        total += nums[i];
    }

    if (target > total || target < -total) {
        return 0;
    }

    if ((target + total) % 2 != 0) {
        return 0;
    }

    int positive = (target + total) / 2;

    int* dp = malloc((positive + 1) * sizeof(int));

    for (int j = 0; j <= positive; j++) {
        dp[j] = 0;
    }

    dp[0] = 1;

    for (int i = 0; i < numsSize; i++) {
        int x = nums[i];

        for (int j = positive; j >= x; j--) {
            dp[j] += dp[j - x];
        }
    }

    int ans = dp[positive];

    free(dp);

    return ans;
}

11. 为什么 j 要倒序？

因为这是：

01 背包

每个数只能选一次。

如果正序：

for (int j = x; j <= positive; j++)

会导致当前 x 被重复使用。

倒序：

for (int j = positive; j >= x; j--)

可以保证：

dp[j - x] 还是上一轮的结果

也就是当前数字只用一次。

12. 目标和易错点
    易错点 1：方案数问题用加法

目标和问：

有多少种方案

所以转移是：

add + sub

或者：

$$dp[j] += dp[j - x]$$

不是 max。

易错点 2：target 可能是负数

如果用记忆化搜索，sum 可能为负数，要加偏移量。

sum + total
易错点 3：背包转换时要判断奇偶

如果：

target + total

是奇数，那么：

$$positive = (target + total) / 2$$

不是整数，直接返回 0。

易错点 4：背包容量是 positive

不是 target。

是：

$$positive = (target + total) / 2$$

13. 题型总结
    494 目标和：

题型：
计数 DP / 01 背包方案数

递归定义：
dfs(i, sum)
表示处理到第 i 个数，当前和为 sum，最后凑成 target 的方案数。

递归转移：
dfs(i, sum)
= dfs(i + 1, sum + nums[i])
+ dfs(i + 1, sum - nums[i])

背包转换：

$$positive - negative = target$$ $$positive + negative = total$$ $$positive = (target + total) / 2$$

转换后：
从 nums 中选一些数，使和为 positive，求方案数。

背包状态：
dp[j] 表示凑出 j 的方案数。

转移：

$$dp[j] += dp[j - nums[i]]$$

遍历：
j 倒序。

一句话：

目标和的本质是：每个数前面选 + 或 -，计数所有能到 target 的路径；也可以转成 01 背包的选数方案数。
三、两个题放一起对比
题目 问什么 决策 转移核心
198 打家劫舍 最大收益 偷 / 不偷 max
494 目标和 方案数量 加正号 / 加负号 +

最重要区别：

问最大值：用 max。
问最小值：用 min。
问方案数：用加法。

DP 不是背公式，先看题目问的是哪种答案。