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

70. 爬楼梯（20250227更新）⭐️

标签：动态规划

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

记忆化搜索

分类思考：

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

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

通项公式：

dfs(i) = dfs(i-1) + dfs(i-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 = new int[n + 1];

        Arrays.fill(f, 0);
        // 这里我把n=1，n=2当作base case，你也可以把n=0，n=1当作base case， f[0] = 1(原地不动一种方法), f[1] = 1
        f[1] = 1;
        f[2] = 2;

        for (int i = 3; 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

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])

递归边界：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)

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

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]

1.2、打家劫舍

494. 目标和（20250407更新）⭐️ 【01背包】

给你一个非负整数数组 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

Changelog

Last Updated: View All Changelog

37044-
feat(sci): encomic: 复盘
On 4/12/25

七、动态规划

一、入门dp

1.1、爬楼梯

126. 斐波那契数（20240227更新）

70. 爬楼梯（20250227更新）⭐️

记忆化搜索

递推

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

377. 组合总和 Ⅳ（20250228更新）

1.2、打家劫舍

494. 目标和（20250407更新）⭐️ 【01背包】

322. 零钱兑换（20250407更新）⭐️【完全背包】

198. 打家劫舍（20241027）

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

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

二、网格图dp

Changelog

求求了，快滚去学习！！！