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

这里重新开始学习动态规划。

为什么要学动态规划，因为智能排产要用得到，之前是看东哥的网站，现在会员过期了，转战看灵神的题解。

MD 数学公式：使用 MD 语法编写数学公式

一、动态规划的理解

这里主要是参考灵神在力扣上面文章，内容如下：

分享丨【题单】动态规划（入门/背包/状态机/划分/区间/状压/数位/树形/数据结构优化）

视频： 动态规划入门：从记忆化搜索到递推

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

动态规划是求的全局最优解。

1.1、参考内容

第14章：动态规划

动态规划解题套路框架

动态规划框架套路详解

二、动态规划的题目总结

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的范围之内，避免数据类型溢出。

322. 零钱兑换（20241027）

给你一个整数数组 coins，表示不同面额的纸币；以及一个整数 amount，表示总金额。计算并返回可以凑成总金额所需要的最少的硬币个数，如果没有任何一种硬币组合能够组成总金额，返回-1.每种硬币的数量是无限的。

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

这里就套用 labuladong 在网站上写的迭代求解最值的框架

// define dp
int[] dp = new dp[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];

通项公式：

$$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 的时候就是求最小值。

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)

JS

Code...

70. 爬楼梯（20250227）

理解题目：假设你在爬楼梯。需要n阶你才能达到楼顶。每次你可以爬1或者2个台阶。你有多少种不同的方法可以爬到楼顶呢？

记忆化搜索

分类思考：

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

这样子就变成了原来问题相同的问题了。

爬1阶和爬2阶都是有可能的，所以使用相加 -> f(n-1) + f(n-2)

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

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), 这些项， 我们可以使用一个数组来缓存

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)

递推

转化成递推公式。

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

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

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

如果最后走的是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])$$

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)

怎么使用递推来解决问题？

因为我们知道状态转移方程了。

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）

题目：给你一个由不同整数组成的数组nums，和一个目标整数target，请你从nums中找出并返回总和为target的元素组合的个数，（题目数据保证答案符合32位整数范围，顺序不同的序列被视作不同的组合）。

和爬楼梯一样，定义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])$$

记忆化搜索

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)

递推

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]

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

Changelog

Last Updated: View All Changelog

• 3d2e0-

  feat(wiki): algo: 算法总结

  On 3/30/25