灵神题解：动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）

灵神B站视频：买卖股票的最佳时机【基础算法精讲 21】

0-1背包 完全背包【基础算法精讲 18】

前言

（当前文章，主要是学习灵神的文章）

掌握动态规划（DP）是没有捷径的，咱们唯一能做的，就是投入时间猛猛刷题。好比数学，只看书看视频而不做习题，是不能说学会的。

我能做的，是帮你节省找题的时间，并把这些题分类整理好，有着相同套路的题，一起做效率会更高，也更能领悟到DP的精髓，所以推荐按照专题刷。

题目已按照难道分排序，如果遇到难度很大，题解都看不懂的题目，结果直接跳过，二刷的时候再来尝试。

记忆话搜索是新手村神器，甚至可以用到游戏后期，推荐先看： 动态规划入门：从记忆化搜索到递推【基础算法精讲 17】

但记忆化搜索并不是万能的，某些题目只有写成递推，才能结合数据结构来优化时间复杂度，多数题目还可以优化空间复杂度，所以尽量在写完记忆话搜索之后，把递推的代码也写一下。熟练之后直接写递推也可以。

一、入门dp

动态规划（DP）是一个重要的算法范式，它是将一个问题分解为一系列更小的子问题，并通过存储子问题的解来避免重复计算，从而大幅提升时间效率。动态规划是求的全局最优解。

1.1、爬楼梯

70. 爬楼梯（20250227）

Details

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

• 1 <= n <= 45

参考灵神题解：教你一步步思考动态规划：从记忆化搜索到递推（Python/Java/C++/Go/JS/Rust）

记忆化搜索

分类思考：

• 如果最后一阶是爬1阶，那么问题就变成了求n-1阶有多少种爬法
• 如果最后一阶是爬2阶，那么问题就变成了求n-2阶有多少种爬法

这样子就变成了原来问题相同的问题了。爬1阶和爬2阶都是有可能的，所以使用相加 -> dfs(i-1) + dfs(i-2)

通项公式：

$$dfs(i) = dfs(i-1) + dfs(i-2)$$

所以纯递归的记忆化搜索代码就可以这样写：

Java递归

class Solution {
    public int climbStairs(int n) {
        return dp(n);
    }

    public int dp(int n){
        if(n == 1 || n == 2){
            return n;
        }
        return dp(n-1) + dp(n-2);
    }
}

Python递归

class Solution:
    def climbStairs(self, n: int) -> int:
        def dfs(i: int):
            if i <= 1:
                return 1
            return dfs(i - 1) + dfs(i - 2)

        return dfs(n)

我们在来看一下，你会发现dfs(i-1)或者dfs(i-2)或有很多重复的项， 假如n=9， f(n-1)会计算f(8), f(7),f(6),f(5)..., f(n-2)也会计算f(7),f(6), 这些项， 我们可以使用一个数组来缓存

Java 记忆化搜索

class Solution {
    int[] memo;

    public int climbStairs(int n) {
        // 1 <= n < 45
        // n 阶台阶，一次走1个或者2个
        // 最后一步走一阶， 就剩n-1阶，最后一步走2阶，就剩n-2阶

        // dfs(i) = dfs(i-1) + dfs(i-2)
        // 为什么是加，因为是最一步可以，走两步也可以，这是两种不同的方法
        memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return dfs(n);
    }

    int dfs(int i) {
        // 表示从0爬到第i阶有多少种方法
        if (i == 1 || i == 2) {
            return i;
        }

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

Python 记忆化搜索

class Solution:
    def climbStairs(self, n: int) -> int:
        cache = [-1] * (n + 1)

        def dfs(i: int):
            if i <= 1:
                return 1
            if cache[i] != -1:
                return cache[i]
            val = dfs(i - 1) + dfs(i - 2)
            cache[i] = val
            return val

        return dfs(n)

递推

转化成递推公式。

Java 递推

class Solution {
    public int climbStairs(int n) {
        // 为什么是n+1，因为是从1到第n阶，总共n个数
        // 如果定义成int[] f = new int[n]的话，没办法直接取f[n],需要将坐标都向前移动一位,为了方便，就定义成 n+1

        // int[] f会设置默认值
        int[] f = new int[n + 1];
        f[0] = 1;
        f[1] = 1;

        for (int i = 2; i <= n; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f[n];
    }
}

Python 递推

class Solution:
    def climbStairs(self, n):
        f = [-1] * (n + 1)
        f[0] = 1
        f[1] = 1

        for i in range(2, n + 1):
            f[i] = f[i - 1] + f[i - 2]
        return f[n]

我们也可以使用两个变量来保存

class Solution:
    def climbStairs(self, n):
        f0 = 1
        f1 = 1
        for _ in range(2, n+1):
            new_f = f0 + f1
            f0 = f1
            f1 = new_f
        return f1

...

126. 斐波那契数（20240227）

斐波那契数是使用动态规划的最好方式。

$$f(n) = \left\{ \begin{matrix} 1,n=1,2 \\ f(n-1) + f(n-2), n>2 \end{matrix} \right.$$

自顶项下求解

class Solution:
    def fib(self, n: int) -> int:
        
        dp = [-1] * (n+1)
        
        def dfs(i):
            if i == 0:
                return 0
            if i == 1:
                return 1
            if dp[i] != -1:
                return dp[i]
            dp[i] = dfs(i-1) + dfs(i-2)
            return dp[i]

        return dfs(n) % 1000000007

自底向上求解

class Solution:
    def fib(self, n: int) -> int:
        if n == 0 or n == 1:
            return n

        # 直接递推
        f0 = 0
        f1 = 1

        for i in range(2, n + 1):
            new_f = f0 + f1
            f0 = f1
            f1 = new_f

        return f1 % 1000000007

模数1000000007是一个常用的质数，它是算法题中经常被用来对结果进行取模的运。这样做的原因是，对于一个很大的数，他的计算结果可能会超出计算机的存储范围，而对一个数取模的话可以将其限制在一个较小的范围内，避免计算结果溢出的问题，100000007是最小的十位数的质数，对结果进行1000000007取模，可以保证值永远在int的范围之内，避免数据类型溢出。

746. 使用最小花费爬楼梯（20250227）

Details

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1：

输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。

示例 2：

输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

提示：

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

如何才能一步一步的解决动态规划问题？

如果最后走的是1步，那么就是求前面n-1个数据的结果；如果最后走的是2步，那么就是求前面n-2个数据的结果，求这两种情况下的最小的花费。

定义dp数据含义就是，求【从0或者1爬到i，定义从0或者1爬到i的最小花费】。

$$min(dfs(i-1) + cost[i-1], dfs(i-2) + cost[i-2])$$

递归边界：dfs(0) = 0, dfs(1) = 0，爬到0或者1阶不需要花费，因为我们一开始在0或者1

递归入口：dfs(n)，也就是答案

Java记忆化搜索

class Solution {
    int[] memo;
    int[] cost;

    public int minCostClimbingStairs(int[] cost) {
        // 定义递归函数含义？dfs(i, cost) 
        // 到顶最少的花费
        int n = cost.length;
        this.cost = cost;
        memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return dfs(n);
    }

    // 利用返回值？递归函数可以传参，也可以利用返回值。
    // 表示从0或者1到i阶，最少的花费cost
    int dfs(int i) {
        // 如何思考递归边界？
        // dfs(0) = 0, dfs(1) = 0.爬到0或者1阶不需要花费，因为我们一开始在0或者1.
        if (i <= 1) {
            return 0;
        }
        if (memo[i] != -1) {
            return memo[i];
        }
        return memo[i] = Math.min(dfs(i - 1) + cost[i - 1], dfs(i - 2) + cost[i - 2]);
    }
}

Python记忆化搜索

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        # 定义dp缓存数组
        dp = [-1] * (n+1)
        def dfs(i):
            if i <= 1:
                return 0
            # 如果存在的话就直接返回
            if dp[i] != -1:
                return dp[i]
            # 状态转移
            min_val = min(dfs(i-1) + cost[i-1], dfs(i-2) + cost[i-2])
            dp[i] = min_val
            return min_val
        return dfs(n)

怎么使用递推来解决问题？因为我们知道状态转移方程了。

Java递推

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] f = new int[n + 1];
        f[0] = 0;
        f[1] = 0;
        for (int i = 2; i <= n; i++) {
            f[i] = Math.min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]);
        }
        return f[n];
    }
}

Python递推

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        # dp数组的含义？表示从0或者1爬到i的最小花费
        dp = [-1] * (n+1)

        # 递推函数
        # f[i] = min(f[i-1] + cost[i-1], f[i-2] + cost[i-2])

        # 还有这里的初始值是怎样确定的？
        dp[0] = dp[1] = 0
        # 边界为什么是n+1, 要求n层，当前位置也算一阶
        for i in range(2, n+1):
            dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
        return dp[n]

377. 组合总和 Ⅳ（20250228）

Details

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：

输入：nums = [9], target = 3
输出：0

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 1000
• nums 中的所有元素 互不相同
• 1 <= target <= 1000

**进阶：**如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

和爬楼梯一样，定义dfs(i)表示爬i个台阶的方案数。（组合总和这里i就是表示列表中的数，target就表示总阶层）

考虑最后一步爬x=nums[j]个台阶，那么问题就变成了i-x个台阶的方案数，即dfs(i-x)。

$$dfs(i) = \sum_{j=0}^n dfs(i-nums[j])$$

如果nums[j] > i 则跳过（因为nums[j] > i 就表示爬多了已经超过了中的target）。

回顾一下，70那题可以看作nums = [1,2]，所以有：

$$dfs(i) = dfs(i-1) + dfs(i-2) = \sum_{j=0}^1 dfs(i - nums[j])$$

Java记忆化搜索

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] memo = new int[target + 1];
        Arrays.fill(memo, -1);
        return dfs(target, nums, memo);
    }

    public int dfs(int i, int[] nums, int[] memo) {
        if (i == 0) {
            return 1;
        }
        if (memo[i] != -1) {
            return memo[i];
        }
        // 枚举所有可以爬的台阶数
        int res = 0;
        for (int x : nums) {
            if (x <= i) {
                res += dfs(i - x, nums, memo);
            }
        }
        return memo[i] = res;
    }
}

Python记忆化搜索

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [-1] * (target + 1)

        # i 表示需要爬的阶数，也就是剩余target
        def dfs(i):
            if i == 0:
                return 1
            
            if dp[i] != -1:
                return dp[i]
            res = sum(dfs(i-x) for x in nums if i >= x)
            dp[i] = res
            return res
        return dfs(target)

递推

Java递推

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] f = new int[target + 1];
        f[0] = 1;

        for (int i = 1; i <= target; i++) {
            for (int x : nums) {
                if (x <= i) {
                    f[i] += f[i - x];
                }
            }
        }
        return f[target];
    }
}

Python递推

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [-1] * (target+1)
        dp[0] = 1
    
        for i in range(1, target+1):
            # for x in nums就是从nums选要爬的阶数
            dp[i] = sum(dp[i-x] for x in nums if x <= i)
        return dp[target]

1.2、打家劫舍

494. 目标和（20250407）

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

就是在给出的数组元素前面添加+或者-，求结果满足target的个数。

题目需要转换一下：

设：

• s表示所有元素的和

• p表示所有添加+的元素和

• s-p表示所有添加-的元素和

• p - (s-p) = |t| -> 就可以得到p=(s+|t|) / 2

就可以达到dfs(i, c)表示从nums[0] 到nums[i]元素中选取元素使结果和等于c。

$$dfs(i, t) = dfs(i-1, t-nums[i]) + dfs(i-1, t)$$

Java

class Solution {
    int[] nums;
    int[][] memo;

    public int findTargetSumWays(int[] nums, int target) {
        // 添加+的数的总和为p
        // 添加-的数的总和为 s-p
        // p - (s-p) = |t|  // t可以小于0，也可以大于0
        // p = (s+|t|)/2

        // 所以就得到：求从nums中选择一些数，使得他们的总和等于(s+t)/2
        this.nums = nums;
        for (int x : nums) {
            target += x;
        }
        // 因为s+t/2，所以s+t不能是奇数
        // 如果全取负号都没办法平替target的话，也直接返回0
        if (target < 0 || target % 2 == 1) {
            return 0;
        }
        int n = nums.length;
        memo = new int[n][target / 2 + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dfs(n - 1, target / 2);
    }

    int dfs(int i, int t) {
        // 如果i小于0，需要判断此时t是否为0
        if (i < 0) {
            return t == 0 ? 1 : 0;
        }
        if (memo[i][t] != -1) {
            return memo[i][t];
        }
        if (t < nums[i]) { // 目标值小于元素，只能不选
            return memo[i][t] = dfs(i - 1, t); // 因为是要求dfs(i, t)所以memo中保存的就是memo[i][t],不用改变下标。
        }
        return memo[i][t] = dfs(i - 1, t - nums[i]) + dfs(i - 1, t); // 选+不选
    }
}

322. 零钱兑换（20250407）

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

求凑成总金额的最少硬币数（硬币个数无限）。

记忆化搜索的公式 ：

$$dfs(i, c) = min(dfs(i-1, c), dfs(i, c-nums[i]) + 1)$$

存在最优子问题，比如 amount = 11， 那么10、9、6 还是按照当时 11 一样的思路来解决。子问题和问题一样。硬币的数量也是无限的。

动态规划解题套路框架

通项公式：

$$dp(n) = \left\{ \begin{matrix} 0, n=0 \\ -1,n<0 \\ min\{dp(n-coin)+1 | coin \in coins\}, n>0 \end{matrix} \right.$$

就是说 amount=0 时结果等于 0， amount<0 时结果-1， amount>0 的时候就是求最小值。

灵神-记忆化搜索

class Solution {
    //              不选                选
    // dfs(i, c) = min(dfs(i-1, c), dfs(i, c - nums[i]) + 1)
    int[] coins;
    int[][] memo;

    public int coinChange(int[] coins, int amount) {
        this.coins = coins;
        int n = coins.length;
        memo = new int[n][amount + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
      	// 判断最后的值是否等于Integer.MAX_VALUE，如果是返回-1，表示凑不出来
        int ans = dfs(n - 1, amount);
        return ans < Integer.MAX_VALUE / 2 ? ans : -1;
    }

    int dfs(int i, int c) {
        if (i < 0) {
          	// 为什么c==0时返回0？表示不再需要凑金币了
            return c == 0 ? 0 : Integer.MAX_VALUE / 2;  // Integer.MAX_VALUE/2防止溢出
        }
        if (memo[i][c] != -1) {
            return memo[i][c];
        }
        if (c < coins[i]) {
            // 只能不选
            return memo[i][c] = dfs(i - 1, c);
        }
        // 不选跳过这个数，所以是i-1
        // 选的话，这个数还可以选，所以是i
        return memo[i][c] = Math.min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1);
    }
}

labuladong递推

class Solution {
    public int coinChange(int[] coins, int amount) {
        // define dp
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1); // 为啥都赋值为amoun+1
        // base case
        dp[0] = 0;
        //
        for (int i = 0; i < dp.length; i++) { // 这里只用了下标，没有用里面的值， 下标就是表示需要凑成的钱
            for (int coin : coins) {
                if (i - coin < 0) { // 表示不能用这个硬币来凑
                    continue;
                }
                dp[i] = Math.min(dp[i], 1 + dp[i - coin]); // 总金额 - 选择的金额求最小值
            }
        }
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
}

...

198. 打家劫舍（20241027）

题目给出一个数组表示第 i 个房间的金额，不能去相邻下标的值，求所获取的最大的金额数。

从后往前看，如果在 i 的位置上，如果选择的话，那就变成了在就 i-2 之前的最大值；如果不选就是求 i-1 最前的下标的最大值。

加备忘录，就是把计算过得值存起来。

Java

class Solution {
    int[] cache;
    public int rob(int[] nums) {
        cache = new int[nums.length];
        Arrays.fill(cache, -1);
        return dfs(nums, nums.length-1);
    }

    public int dfs(int[] nums, int i){
        if(i<0){
            return 0;
        }
        if(cache[i] != -1){
            return cache[i];
        }
        int res = Math.max(dfs(nums, i-1), dfs(nums, i-2) + nums[i]);
        cache[i] = res;
        return cache[i];
    }
}

Python

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        cache = [-1] * n 

        def dfs(i):
            if i < 0:
                return 0
            if cache[i] != -1:
                return cache[i]
            
            val = max(dfs(i-1), dfs(i-2) + nums[i])
            cache[i] = val
            return val
        
        return dfs(n-1)

2466. 统计构造好字符串的方案数（20250228）

简单描述一下题目：就是题目给出整数zero, one, low, high, 从空字符串开始，每次可以执行下面两个操作：

• 将 '0' 在字符串末尾添加 zero 次。
• 将 '1' 在字符串末尾添加 one 次。

如果通过上面的操作得到的字符串长度在[low, high]之间，表示时候好字符串，求这种字符串的个数

记忆化搜索

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        # 定义f[i]表示构造长为i的字符串的方案数，其中构造空串的方案数为1，即f[0] = 1
        mod = 1_000_000_007
        @cache
        def dfs(i):
            if i < 0:
                return 0
            if i == 0:
                return 1
            
            ans = dfs(i-zero) + dfs(i-one)
            return ans % mod
        return sum(dfs(i) for i in range(low, high+1)) % mod

递推

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        MOD = 1_000_000_007
        f = [-1] * (high + 1)
        
        # 初始条件
        f[0] = 1

        for i in range(1, high+1):
            # 当i<zero 或者i<one的时候都不满足好字符串，直接跳过
            if i >= zero:
                f[i] = f[i-zero] % MOD
            if i >= one:
                f[i] = (f[i] + f[i-one]) %MOD
        return sum(f[low:]) % MOD

122. 买卖股票的最佳时机 II（20250403）

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

买卖股票，不限制买卖次数。

需要思考的几个问题：

• 递归的边界条件是什么？

  • 第0天是否持有股票，如果不持有股票dfs(-1, 0) = 0，如果持有股票，dfs(-1, 1)=Integer.MIN_VALUE，因为第0天持有股票是不合理的，就赋值成最小的值，方便求最大值。

• 递推公式是什么？

  • 当第i天不持有股票，两种可能，第i-1天也不持有股票；第二种，第i-1天买出股票，获得利润prices[i]。

    $$dfs(i, 0) = max(dfs(i-1, 0), dfs(i-1, 1) + prices[i])$$

  • 当第i天持有股票，两种可能：第i-1天也持有股票，不做操作；第二种，第i-1天买入股票，花费prices[i]价格。

    $$dfs(i, 1) = max(dfs(i-1, 1), dfs(i-1, 0) + prices[i])$$

• 递归的入口是什么？

  • 求最后一天的利润，两种可能，一种是持有股票dfs(n, 1)，第二种就是不持有股票dfs(n, 0)， 那么肯定是不持有股票获取的利润最多。

递归+保存计算结果=记忆化搜索

class Solution {
    private int[] prices;

    // 备忘录来解决重复计算问题
    private int[][] memo;

    public int maxProfit(int[] prices) {
        this.prices = prices;
        int n = prices.length;
        memo = new int[n][2];
        for (int[] row : memo) {
            Arrays.fill(row, -1); // -1 表示还没有计算过
        }
        return dfs(n - 1, 0); // 为什么是n-1，因为我们的下标是从0开始的，n-1就是最后一天
    }

    int dfs(int i, int hold) {
        // 非规范化
        if (i < 0) {
            return hold == 1 ? Integer.MIN_VALUE : 0;
        }

        // 规范化
        // 之前计算过
        if (memo[i][hold] != -1) {
            return memo[i][hold];
        }
        if (hold == 1) {
            return memo[i][hold] = Math.max(dfs(i - 1, 1), dfs(i - 1, 0) - prices[i]);
        }
        return memo[i][hold] = Math.max(dfs(i - 1, 0), dfs(i - 1, 1) + prices[i]);
    }
}

递推

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] f = new int[n + 1][2];

        f[0][1] = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            f[i + 1][0] = Math.max(f[i][0], f[i][1] + prices[i]);
            f[i + 1][1] = Math.max(f[i][1], f[i][0] - prices[i]);
        }
        return f[n][0];

    }
}

二、网格图dp

2.1 基础

2.2 进阶

三、背包

讲解：0-1 背包 完全背包【基础算法精讲 18】

3.1、0-1 背包

每个物品只能选一次。

选或者不选

• 0-1背包（目标和，回溯，记忆话搜索，递推，空间优化：两个数组；空间优化：一个数组）
• 完全背包（零钱兑换）
• 常见变形

0-1背包：有n个物品，第i个物品的体积是w[i]， 价值是v[i]，每个物品最多选一个，求体积和不超过capacity时的最大价值和。

回溯三问：

• 当前操作？枚举第i个物品选或者不选；不选，剩余容量不变；选，剩余容量减少w[i]
• 子问题？在剩余容量为c时，从前i个物品中得到的最大价值和
• 下一个子问题？分类讨论：不选：在剩余容量为c时，从前i-1个物品中得到的最大价值和；选：在剩余容量为c-w[i]时，从前面i-1个物品中得到的最大价值和。

$$dfs(i, c) = max(dfs(i-1,c), dfs(i-1, c - w[i])+v[i])$$

494. 目标和（20250804）

Details

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

输入：nums = [1], target = 1
输出：1

提示：

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

根据题意就是在数组元素前面添加加好或者减号，实得最后的结果等于目标值。

记忆化搜索

class Solution {

    public int findTargetSumWays(int[] nums, int target) {
        // p = (s+t)/2 
        // 从nums中选择一些数刚好等于p
        int s = 0;
        for (int x : nums) {
            s += x;
        }
        s -= Math.abs(target);
        if (s < 0 || s % 2 != 0) {
            return 0;
        }
        int t = s / 2;
        int n = nums.length;
        int[][] memo = new int[n + 1][t + 1];
        for (int[] r : memo) {
            Arrays.fill(r, -1);
        }
        return dfs(n - 1, t, nums, memo);
    }

    public int dfs(int i, int t, int[] nums, int[][] memo) {
        if (i < 0) {
            return t == 0 ? 1 : 0;
        }
        if (memo[i][t] != -1) {
            return memo[i][t];
        }
        int res = dfs(i - 1, t, nums, memo);
        if (t >= nums[i]) {
            res += dfs(i - 1, t - nums[i], nums, memo);
        }
        return memo[i][t] = res;
    }
}

1:1翻译成递推

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int s = 0;
        for (int x : nums) {
            s += x;
        }
        s -= Math.abs(target);
        if (s < 0 || s % 2 == 1) {
            return 0;
        }

        int m = s / 2;
        int n = nums.length;
        int[][] f = new int[n + 1][m + 1];

        f[0][0] = 1;

        for (int i = 0; i < n; i++) {
            for (int c = 0; c <= m; c++) {
                if (nums[i] > c) {
                    f[i + 1][c] = f[i][c];
                } else {
                    f[i + 1][c] = f[i][c] + f[i][c - nums[i]];
                }
            }
        }
        return f[n][m];
    }
}

416. 分割等和子集（20250803）

Details

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

参考灵神的题解：三种写法：记忆化搜索 / 递推 / bitset 优化（Python/Java/C++/C/Go/JS/Rust）

记忆化搜索

class Solution {
    public boolean canPartition(int[] nums) {
        // 从nums中能选择元素，组成结果s/2
        int s = 0;
        for (int x : nums) {
            s += x;
        }
        if (s % 2 != 0) {
            return false;
        }

        int m = s / 2;
        int n = nums.length;
        int[][] memo = new int[n][m + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dfs(n - 1, s / 2, nums, memo);
    }

    // 不知道返回什么？
    // 定义 dfs函数的含义？ dfs(i, m) 表示从0到i能否选择和为m的子序列
    public boolean dfs(int i, int m, int[] nums, int[][] memo) {
        if (i < 0) {
            return m == 0;
        }
        if (memo[i][m] != -1) {
            return memo[i][m] == 1;
        }

        // 只有m>=nums[i]才能选
        boolean res = m >= nums[i] && dfs(i - 1, m - nums[i], nums, memo) || dfs(i - 1, m, nums, memo);
        memo[i][m] = res ? 1 : 0;
        return res;
    }
}

递推

class Solution {
    public boolean canPartition(int[] nums) {
        int s = 0;
        for (int x : nums) {
            s += x;
        }
        if (s % 2 != 0) {
            return false;
        }
        int n = nums.length;
        s /= 2;
        boolean[][] f = new boolean[n + 1][s + 1];

        f[0][0] = true;

        for (int i = 0; i < n; i++) {
            int x = nums[i];
            for (int j = 0; j <= s; j++) {
                f[i + 1][j] = j >= x && f[i][j - x] || f[i][j];
            }
        }
        return f[n][s];
    }
}

四、经典线性DP

4.1、最长公共子序列（LCS）

一般定义$f[i][j]$表示$(s[:i], t[:j])$的求解结果。

4.1.1 基础

1143. 最长公共子序列（20250810）

Details

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

示例 3：

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

提示：

• 1 <= text1.length, text2.length <= 1000
• text1 和 text2 仅由小写英文字符组成。

求最长子序列，子数组和子串是连续的，子序列不一定连续。

问题就变成了，对于text1和text2的每一个字符比较，选或者不选的问题，假设s和t分别是text1和text2的char[]数据。

就变成了， s[i] 与t[j]是否相等，相等的话，就选择；否则的话，就求s[i-1]和t[j] 与s[i]和t[j-1]的最大值，得到下面公式：

Java

class Solution {
    private char[] s, t;
    private int[][] memo;

    public int longestCommonSubsequence(String text1, String text2) {
        s = text1.toCharArray();
        t = text2.toCharArray();

        int n = s.length, m = t.length;
        memo = new int[n][m];
        for (int[] x : memo) {
            Arrays.fill(x, -1);
        }
        return dfs(n - 1, m - 1);
    }

    public int dfs(int i, int j) {
        if (i < 0 || j < 0) {
            return 0;
        }
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        if (s[i] == t[j]) {
            return memo[i][j] = dfs(i - 1, j - 1) + 1;
        }
        return memo[i][j] = Math.max(dfs(i - 1, j), dfs(i, j - 1));
    }
}

72. 编辑距离（20250810）

Details

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示：

• 0 <= word1.length, word2.length <= 500
• word1 和 word2 由小写英文字母组成

对于题目来说，还是很好理解的，就是把word1转换成word2最少的操作次数，如果解决才是问题。

s和t分别表示word1和word2 char[]

问题就转化成了s[i] 和t[j]的操作，如果s[i] == t[j]，就转化成子问题s[i-1] 与t[j-1]的关系。

所以就得到一个公式

• s[i] == t[j], dfs(i-1, j-1)
• s[i] != t[j], min(dfs(i, j-1), dfs(i-1, j), dfs(i-1, j-1)) + 1

dfs(i, j-1)就表示插入

dfs(i-1, j)就表示删除

dfs(i-1, j-1) 就表示替换

Java

class Solution {
    private char[] s, t;
    private int[][] memo;
    public int minDistance(String word1, String word2) {
        int n = word1.length(), m = word2.length();
        s = word1.toCharArray();
        t = word2.toCharArray();
        memo = new int[n][m];
        for (int[] x : memo) {
            Arrays.fill(x, -1);
        }
        return dfs(n - 1, m - 1);
    }

    private int dfs(int i, int j) {
        if (i < 0) {
            return j + 1;
        }
        if (j < 0) {
            return i + 1;
        }
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        if (s[i] == t[j]) {
            return memo[i][j] = dfs(i - 1, j - 1);
        }
        return memo[i][j] = Math.min(Math.min(dfs(i, j - 1), dfs(i - 1, j)), dfs(i - 1, j - 1)) + 1;
    }
}

Changelog

8/20/25, 11:06 AM

View All Changelog

• 4c155-Merge branch 'dev1'on 8/20/25