算法-动态规划(记忆化搜索)、递推.md

动态规划(记忆化搜索)、递推

理解

• 动态规划是记忆化搜索的一种特殊形式；
• 一般思路：当子问题的结果需要被重复利用（存在大量重复计算） -> 记忆化搜索 -> 动态规划（迭代）；

步骤

状态定义

转移方程

初始状态

难点

• 动态规划关键是找到初始状态和状态转移方程；
  • 有些问题的状态并不是问题本身，需要重新构造，也是一个难点；

Problems

• LeetCode 0005 最长回文子串 (中等, 2021-10)
• LeetCode 0010 正则表达式匹配 (困难, 2022-01)
• LeetCode 0053 最大子数组和 (简单, 2022-01)
• LeetCode 0064 最小路径和 (中等, 2022-01)
• LeetCode 0070 爬楼梯 (简单, 2022-01)
• LeetCode 0072 编辑距离 (困难, 2022-01)
• LeetCode 0091 解码方法 (中等, 2022-02)
• LeetCode 0096 不同的二叉搜索树 (中等, 2022-03)
• LeetCode 0120 三角形最小路径和 (中等, 2022-01)
• LeetCode 0121 买卖股票的最佳时机 (简单, 2022-01)
• LeetCode 0122 买卖股票的最佳时机II (中等, 2022-01)
• LeetCode 0123 买卖股票的最佳时机III (困难, 2022-01)
• LeetCode 0152 乘积最大子数组 (中等, 2022-01)
• LeetCode 0198 打家劫舍 (中等, 2022-02)
• LeetCode 0213 打家劫舍II (中等, 2022-02)
• LeetCode 0300 最长递增子序列 (中等, 2022-01)
• LeetCode 0322 零钱兑换 (中等, 2022-02)
• LeetCode 0343 整数拆分 (中等, 2021-12)
• LeetCode 0518 零钱兑换II (中等, 2022-02)
• 剑指Offer 1001 斐波那契数列 (简单, 2021-11)
• 剑指Offer 1001 斐波那契数列 (简单, 2021-11)
• 剑指Offer 1002 跳台阶 (简单, 2021-11)
• 剑指Offer 1401 剪绳子（整数拆分） (中等, 2021-11)
• 剑指Offer 1900 正则表达式匹配 (困难, 2021-11)
• 剑指Offer 4200 连续子数组的最大和 (简单, 2021-12)
• 剑指Offer 4600 斐波那契数列-3（把数字翻译成字符串） (中等, 2021-12)
• 剑指Offer 4700 礼物的最大价值 (中等, 2021-12)
• 剑指Offer 4800 最长不含重复字符的子字符串 (中等, 2021-12)
• 剑指Offer 4900 丑数 (中等, 2021-12)
• 剑指Offer 6000 n个骰子的点数 (中等, 2022-01)
• 剑指Offer 6200 圆圈中最后剩下的数字（约瑟夫环问题） (中等, 2022-01)
• 牛客 0017 最长回文子串 (中等, 2022-01)
• 牛客 0019 连续子数组的最大和 (简单, 2022-01)
• 牛客 0034 求路径 (简单, 2022-02)
• 牛客 0035 编辑距离(二) (较难, 2022-02)
• 牛客 0059 矩阵的最小路径和 (中等, 2022-03)
• 牛客 0065 斐波那契数列 (入门, 2022-03)
• 牛客 0068 跳台阶 (简单, 2022-03)
• 牛客 0091 最长上升子序列(三) (较难, 2022-03)
• 牛客 0127 最长公共子串 (中等, 2022-03)
• 牛客 0145 01背包 (中等, 2022-03)

---

LeetCode 0005 最长回文子串 (中等, 2021-10)

问题简述

给你一个字符串 s，找到 s 中最长的回文子串。

5. 最长回文子串 - 力扣（LeetCode）

详细描述

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：
    输入：s = "babad"
    输出："bab"
    解释："aba" 同样是符合题意的答案。
示例 2：
    输入：s = "cbbd"
    输出："bb"
示例 3：
    输入：s = "a"
    输出："a"
示例 4：
    输入：s = "ac"
    输出："a"

提示：
    1 <= s.length <= 1000
    s 仅由数字和英文字母（大写和/或小写）组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：动态规划

• 状态定义：dp[i][j] := 子串 s[i:j] 是否为回文串；
• 状态转移方程：dp[i][j] := dp[i+1][j-1] == True 且 s[i] == s[j]；
• 初始状态
  • 单个字符：dp[i][j] := True 当 i == j
  • 两个连续相同字符：dp[i][j] := True 当 j == i + 1 && s[i] == s[j]

注意：

• 动态规划并不是最适合的解，这里仅提供一个思路；
• 如果要使用动态规划解本题，如何循环是关键，因为回文串的特点，从“双指针”的角度来看，需要从中心往两侧遍历，这跟大多数的 dp 问题略有不同；

C++

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();

        vector<vector<int>> dp(n, vector<int>(n, 0));
        int max_len = 1;    // 保存最长回文子串长度
        int start = 0;      // 保存最长回文子串起点

        // 初始状态1：子串长度为 1 时，显然是回文子串
        for (int i = 0; i < n; i++)
            dp[i][i] = 1;

        //for (int j = 1; j < n; j++)         // 子串结束位置
        //    for (int i = 0; i < j; i++) {   // 子串起始位置
        // 上述循环方式也是可以的，但在 “最长回文子序列” 一题中会有问题
        // 下面的循环方式在两个问题中都正确，这个遍历思路比较像“中心扩散法”
        for (int j = 1; j < n; j++)             // 子串结束位置
            for (int i = j - 1; i >= 0; i--) {  // 子串开始位置
                if (j == i + 1)  // 初始状态2：子串长度为 2 时，只有当两个字母相同时才是回文子串
                    dp[i][j] = (s[i] == s[j]);
                else  // 状态转移方程：当上一个状态是回文串，且此时两个位置的字母也相同时，当前状态才是回文串
                    dp[i][j] = (dp[i + 1][j - 1] && s[i] == s[j]);

                // 保存最长回文子串
                if (dp[i][j] && max_len < (j - i + 1)) {
                    max_len = j - i + 1;
                    start = i;
                }
            }

        return s.substr(start, max_len);
    }
};

Python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        n = len(s)
        dp = [[0] * n for _ in range(n)]

        for i in range(n):
            dp[i][i] = 1
        
        start = 0
        length = 1
        for j in range(1, n):  # 子串的结束位置
            for i in range(j - 1, -1, -1):  # 子串的开始位置
                if i == j - 1:
                    dp[i][j] = 1 if s[i] == s[j] else 0
                else:
                    dp[i][j] = 1 if dp[i + 1][j - 1] and s[i] == s[j] else 0

                if dp[i][j]:
                    if j - i + 1 > length:
                        length = j - i + 1
                        start = i

        return s[start: start + length]

思路2：模拟-中心扩散（推荐）

• 按照回文串的定义，遍历每个字符作为中点，向两边扩散；
• 官方题解从 DP 的转移方程解释了为什么中心扩散可以得到正确答案（虽然这个结论非常直观），观察状态转移方程，可以看到所有状态在转移时的可能性都是唯一的：dp[i][j] <- dp[i+1][j-1] <- dp[i+2][j-2] <- ...，也就是说，从每一种边界情况开始「扩展」，都可以得出所有状态对应的答案。

  最长回文子串 - 力扣官方题解

Python

class Solution:
    def longestPalindrome(self, s: str) -> str:

        n = len(s)
        self.ret = s[0]

        # 从 s[l:r] 开始向两侧扩散，开始时，l==r 或者，l+1==r
        def process(l, r):
            tmp = ''
            while l >= 0 and r < n:
                if s[l] != s[r]:
                    break
                tmp = s[l: r + 1]
                l -= 1
                r += 1

            if len(tmp) > len(self.ret):
                self.ret = tmp

        for l in range(n - 1):
            process(l, l)
            process(l, l + 1)

        return self.ret

---

LeetCode 0010 正则表达式匹配 (困难, 2022-01)

问题简述

请实现一个函数用来匹配包含'.'和'*'的正则表达式。

10. 正则表达式匹配 - 力扣（LeetCode）

思路：动态规划

• 定义 dp(i, j) 表示 s[:i] 与 p[:j] 是否匹配；
• 难点是要把所有情况考虑全面，尤其是初始化，以及 p[j-1] == '*' 的情况；

递归版

class Solution:
    def isMatch(self, s: str, p: str) -> bool:

        from functools import lru_cache

        # 因为本题保证了 p 的合法性，所以可以省略部分边界判断
        @lru_cache(maxsize=None)
        def dp(i, j):
            if i == 0 and j == 0: return True
            if j == 0: return False
            # 空串的判断，比如 s='', p='a*' 或 'a*b*'
            if i == 0: return p[j - 1] == '*' and dp(i, j - 2)

            # 情况1：s='abc', p='abc' 或 'ab.'
            r1 = (s[i - 1] == p[j - 1] or p[j - 1] == '.') and dp(i - 1, j - 1)
            # 情况2：'*'匹配了 0 个字符的情况，比如 s='ab', p='abc*'
            r2 = p[j - 1] == '*' and dp(i, j - 2)
            # 情况3：'*'匹配了 1 个以上的字符，比如 s='abc', p='abc*' 或 'ab.*'
            r3 = p[j - 1] == '*' and (s[i - 1] == p[j - 2] or p[j - 2] == '.') and dp(i - 1, j)
            
            return r1 or r2 or r3

        m, n = len(s), len(p)
        return dp(m, n)

迭代版

class Solution:
    def isMatch(self, s: str, p: str) -> bool:

        m, n = len(s), len(p)
        dp = [[False] * (n + 1) for _ in range(m + 1)]

        # 初始化，对应递归中的 base case
        # dp[0][0] = True
        # for j in range(2, n + 1):
        #     dp[0][j] = p[j - 1] == '*' and dp[0][j - 2]

        # 为了匹配“无缝转换”，把上面的初始化代码也写到了循环里面，两种写法都可以
        for i in range(0, m + 1):
            for j in range(0, n + 1):
                if i == 0 and j == 0: dp[i][j] = True
                elif j == 0: continue
                elif i == 0: dp[i][j] = p[j - 1] == '*' and dp[0][j - 2]
                else:
                    r1 = (s[i - 1] == p[j - 1] or p[j - 1] == '.') and dp[i - 1][j - 1]
                    r2 = p[j - 1] == '*' and dp[i][j - 2]
                    r3 = p[j - 1] == '*' and (s[i - 1] == p[j - 2] or p[j - 2] == '.') and dp[i - 1][j]
                    dp[i][j] = r1 or r2 or r3

        return dp[m][n]

---

LeetCode 0053 最大子数组和 (简单, 2022-01)

问题简述

给定整数数组 nums ，返回连续子数组的最大和（子数组最少包含一个元素）。

详细描述

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：
    输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
    输出：6
    解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
    输入：nums = [5,4,-1,7,8]
    输出：23

提示：
    1 <= nums.length <= 10^5
    -10^4 <= nums[i] <= 10^4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

Python

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        
        # 因为始终只与上一个状态有关，因此可以通过“滚动变量”的方式优化空间
        dp = nums[0]
        ret = nums[0]
        for i in range(1, len(nums)):
            dp = max(nums[i], dp + nums[i])
            ret = max(ret, dp)
        
        return ret

---

LeetCode 0064 最小路径和 (中等, 2022-01)

问题简述

给定一个非负整数的 m x n 网格 grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

64. 最小路径和 - 力扣（LeetCode）

详细描述

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：
    输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
    输出：7
    解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
    输入：grid = [[1,2,3],[4,5,6]]
    输出：12

提示：
    m == grid.length
    n == grid[i].length
    1 <= m, n <= 200
    0 <= grid[i][j] <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：动态规划

Python

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        if not grid: return 0

        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]

        # 初始化
        dp[0][0] = grid[0][0]
        for i in range(1, m):
            dp[i][0] = dp[i - 1][0] + grid[i][0]
        for j in range(1, n):
            dp[0][j] = dp[0][j - 1] + grid[0][j]

        # print(dp)
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        
        return dp[-1][-1]

空间优化：展开循环可以发现，内循环每次遍历实际只会用到上一层的和当前层左边的结果（详见代码）；

Python

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        if not grid: return 0

        m, n = len(grid), len(grid[0])
        dp = [0] * n

        # 初始化
        dp[0] = grid[0][0]
        for j in range(1, n):
            dp[j] = dp[j - 1] + grid[0][j]

        # print(dp)
        for i in range(1, m):
            dp[0] = dp[0] + grid[i][0]  # 初始化每一层最左边的结果
            for j in range(1, n):
                # dp[j - 1] + grid[i][j] 表示从左边移动
                # dp[j] + grid[i][j] 表示从上方移动
                dp[j] = min(dp[j - 1], dp[j]) + grid[i][j]
        
        return dp[-1]

---

LeetCode 0070 爬楼梯 (简单, 2022-01)

问题简述

规定每次可以爬1级或2级台阶。求爬一个 n 级台阶总共有多少种方法。

详细描述

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

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

注意：给定 n 是一个正整数。

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：动态规划

Python

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

        dp1, dp2 = 1, 2
        for _  in range(3, n + 1):
            dp1, dp2 = dp2, dp1 + dp2
        
        return dp2

---

LeetCode 0072 编辑距离 (困难, 2022-01)

问题简述

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

详细描述

给你两个单词 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 由小写英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/edit-distance
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

• 动态规划经典问题 > 编辑距离 - 力扣官方题解

• Tips：“插入”和“删除”操作可以认为是同一种操作，因为编辑距离具有对称性，在一方中插入，等价于在另一方删除，这有助于理解代码；

Python

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:

        m = len(word1)
        n = len(word2)

        if m * n == 0:  # 其中一个是空串
            return m + n
        
        dp = [[0] * (n + 1) for _ in range(m + 1)]  # m * n
        
        for i in range(1, m + 1):
            dp[i][0] = i
        for i in range(1, n + 1):
            dp[0][i] = i
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                r1 = dp[i - 1][j] + 1
                r2 = dp[i][j - 1] + 1
                r3 = dp[i - 1][j - 1]
                if word1[i - 1] != word2[j - 1]:
                    r3 += 1
                dp[i][j] = min(r1, r2, r3)
        
        return dp[m][n]

优化：利用滚动数组将空间复杂度从 O(MN) 优化到 min(O(N), O(M))

Python

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:

        m = len(word1)
        n = len(word2)

        if m * n == 0:  # 其中一个是空串
            return m + n

        if m < n:
            m, n = n, m
            word1, word2 = word2, word1
        
        dp_pre = [0] * (n + 1)
        for i in range(1, n + 1):
            dp_pre[i] = i
        
        for i in range(1, m + 1):
            dp_cur = [i] + [0] * n
            for j in range(1, n + 1):
                r1 = dp_cur[j - 1] + 1
                r2 = dp_pre[j] + 1
                r3 = dp_pre[j - 1]
                if word1[i - 1] != word2[j - 1]:
                    r3 += 1
                dp_cur[j] = min(r1, r2, r3)
            dp_pre = dp_cur
        
        return dp_cur[n]

---

LeetCode 0091 解码方法 (中等, 2022-02)

问题简述

将数字解码成字母，返回可能的解码方法数；
例如，"11106" 可以映射为：
    "AAJF" ，将消息分组为 (1 1 10 6)
    "KJF" ，将消息分组为 (11 10 6)

91. 解码方法 - 力扣（LeetCode）

思路1：从左往右的暴力递归

• 定义 dfs(i) 表示 s[:i] 已经固定的情况下，s[i:] 的解码方法；
• 【递归基】i=n 时，s[:n] 都固定了，即表示找到了一种解法方法；
• 本题的难点是 dfs(i) 不光可以从 dfs(i-1) 递推，还可以从 dfs(i-2) 递推；

  可以看做是有限制的跳台阶问题；

Python

class Solution:
    def numDecodings(self, s: str) -> int:

        from functools import lru_cache  # 记忆化搜索

        n = len(s)  # 字符长度

        @lru_cache(maxsize=None)
        def dfs(i):  # 表示 s[:i] 已经固定的情况下，s[i:] 的解码方法
            if i == n:  # s[:n] 都已经固定，即找到了一种有效的解码方法
                ret = 1
            elif s[i] == '0':  # 以 0 开始的字符不存在有效解码
                ret = 0
            elif s[i] == '1':  # 如果以 1 开头，可以尝试两个位置
                ret = dfs(i + 1)  # 这个 1 已经固定了
                if i + 1 < n:  # 因为 10 ~ 19 都存在有效解码，因此只要后面存在两个字符，就可以加上 dfs(i + 2)
                    ret += dfs(i + 2)
            elif s[i] == '2':  # 如果以 2 开头，可以有条件的尝试两个位置
                ret = dfs(i + 1)
                if i + 1 < n and '0' <= s[i + 1] <= '6':
                    ret += dfs(i + 2)
            else:  # 如果以 3~9 开头，只能尝试一个位置
                ret = dfs(i + 1)

            return ret

        return dfs(0)

思路2：将暴力递归转化为动态规划

• 有了递归过程后，就可以脱离原问题，模板化的将其转化为动态规划。

Python

class Solution:
    def numDecodings(self, s: str) -> int:

        n = len(s)  # 字符长度
        dp = [0] * (n + 1)

        # 初始化（对应递归中的 base case）
        #   i == n 时 ret = 1，即
        dp[n] = 1

        # 递推过程：对应递归过程填空
        #   下面的写法略有冗余，可以做一些合并，但是为了做到跟递归一一对应，就没有修改
        for i in range(n - 1, -1, -1):
            # 为什么是倒序遍历，一方面可以从问题理解；
            #   另一方面可以从递归过程看，因为最后返回的是 dp[0]，同时 dp[i] 需要从  dp[i + 1] 递推，所以显然需要逆序遍历
            if s[i] == '0':
                dp[i] = 0  # ret = 0
            elif s[i] == '1':
                dp[i] = dp[i + 1]  # ret = rec(i + 1)
                if i + 1 < n:
                    dp[i] += dp[i + 2]  # ret += rec(i + 2)
            elif s[i] == '2':
                dp[i] = dp[i + 1]  # ret = rec(i + 1)
                if i + 1 < n and '0' <= s[i + 1] <= '6':
                    dp[i] += dp[i + 2]  # ret += rec(i + 2)
            else:
                dp[i] = dp[i + 1]  # ret = rec(i + 1)

        return dp[0]  # return rec(0)

---

LeetCode 0096 不同的二叉搜索树 (中等, 2022-03)

问题简述

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

96. 不同的二叉搜索树 - 力扣（LeetCode）

思路：动态规划

• 对一个有序数组，无论值是多少，它能构成的方法数都是一样的；
• 对一个长度为 n 的有序数组，取第 i 个值作为根节点，分成左右两个规模分别为 l=i-1 和 r=n-i 的子问题；
  • 则选择该节点作为根节点的方法数 = 左子树的方法数 * 右子树的方法数；
  • 得递推公式： dp(n) = sum( dp(i-1) * dp(n-i) )，其中 i in [1, n+1)；
• 实际上本题就是一个卡特兰数的实例；

Python：递归写法

class Solution:
    def numTrees(self, n: int) -> int:

        from functools import lru_cache

        @lru_cache(maxsize=None)
        def dp(n):
            if n in (0, 1): return 1

            ret = 0
            for i in range(1, n + 1):   # 选择第 i 个数字作为根节点
                l, r = i - 1, n - i     # 此时左右子树的节点个数
                ret += dp(l) * dp(r)    # 左边 l 个节点的方法数 * 右边 r 个节点的方法数
            return ret
        
        return dp(n)

Python：迭代写法（略）

---

LeetCode 0120 三角形最小路径和 (中等, 2022-01)

问题简述

给定一个三角形 triangle ，找出自顶向下的最小路径和。

详细描述

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：
    输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
    输出：11
    解释：如下面简图所示：
    2
    3 4
    6 5 7
    4 1 8 3
    自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
示例 2：
    输入：triangle = [[-10]]
    输出：-10

提示：
    1 <= triangle.length <= 200
    triangle[0].length == 1
    triangle[i].length == triangle[i - 1].length + 1
    -10^4 <= triangle[i][j] <= 10^4
 

进阶：

你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/triangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：动态规划

• 思路跟网格版的最小路径和基本相同，就是路线方向略有不同，模拟路线即可；

Python

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        if not triangle: return 0

        dp = [triangle[0][0]]
        for i in range(1, len(triangle)):
            dp = [dp[0] + triangle[i][0]] + dp  # 加上最左路
            for j in range(1, len(triangle[i])):
                if j == len(triangle[i]) - 1:  # 特殊处理最右路
                    dp[j] = dp[j] + triangle[i][j]
                else:  # 因为提前改变了 dp 的长度，所以不能写成 min(dp[j], dp[j - 1])，这里踩了个小坑
                    dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j]
            
            # print(dp)
        
        return min(dp)

---

LeetCode 0121 买卖股票的最佳时机 (简单, 2022-01)

问题简述

给定数组 prices，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能进行一次买卖。求最大利润。

详细描述

给定一个数组 prices，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：
    输入：[7,1,5,3,6,4]
    输出：5
    解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
        注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
    输入：prices = [7,6,4,3,1]
    输出：0
    解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：
    1 <= prices.length <= 10^5
    0 <= prices[i] <= 10^4


来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：模拟

1. 遍历 prices，以 min_p 记录当前的最小值（非全局最小值）；
2. 用当前价格 p 减去 min_p，得到当天卖出的利润；
3. 使用 ret 记录遍历过程中的最大利润。

• 以上思路只适用于一次买卖的情况；

Python

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        """"""
        ret = 0
        min_p = 10001
        for p in prices:
            min_p = min(p, min_p)
            ret = max(ret, p - min_p)
        
        return ret

---

LeetCode 0122 买卖股票的最佳时机II (中等, 2022-01)

问题简述

给定数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

详细描述

给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:
    输入: prices = [7,1,5,3,6,4]
    输出: 7
    解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
        随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
    输入: prices = [1,2,3,4,5]
    输出: 4
    解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
        注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
    输入: prices = [7,6,4,3,1]
    输出: 0
    解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：
    1 <= prices.length <= 3 * 10^4
    0 <= prices[i] <= 10^4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：动态规划

TODO

Python

思路2：贪心

买卖股票的最佳时机 II - 力扣官方题解

• 考虑一共有三种情况：
  1. 有涨有跌：只有连续两天交易的收益为正，就应该交易；
  2. 连续上涨：按题意应该在头尾交易一次，但注意到：$p_3-p_1$等价于$(p_3-p_2)+(p_2-p_1)$，换言之，等价于当天买入，次日卖出再买入（实际计算过程不等于交易过程）
  3. 连续下跌：不交易
• 综上：比较连续两天的价格，只要收益为正，就交易；

Python

class Solution:
    def maxProfit(self, prices: List[int]) -> int:

        ret = 0
        for i in range(1, len(prices)):
            dif = prices[i] - prices[i - 1]
            if dif > 0:
                ret += dif

        return ret

---

LeetCode 0123 买卖股票的最佳时机III (困难, 2022-01)

问题简述

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

详细描述

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:
    输入：prices = [3,3,5,0,0,3,1,4]
    输出：6
    解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
        随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2：
    输入：prices = [1,2,3,4,5]
    输出：4
    解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
        注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
        因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3：
    输入：prices = [7,6,4,3,1] 
    输出：0 
    解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
示例 4：
    输入：prices = [1]
    输出：0

提示：
    1 <= prices.length <= 10^5
    0 <= prices[i] <= 10^5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：动态规划

• 分别定义前向、后向两个dp，记 dp_f 和 dp_b，其中：
  • dp_f[i] 表示 prices[:i] 区间内的买卖一次的最大值；
  • dp_b[i] 表示 prices[i:] 区间内的买卖一次的最大值；
• 因为可以只交易一次，所以最终结果为 max(dp_f[-1], max(dp_f[i] + dp_b[i + 1]))

Python

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) < 2: return 0
        
        n = len(prices)
        dp_f = [0] * n
        dp_b = [0] * n

        min_p = prices[0]
        for i in range(1, n):
            dp_f[i] = max(dp_f[i-1], prices[i] - min_p)
            min_p = min(min_p, prices[i])
        
        max_b = 0
        max_p = prices[-1]
        for i in range(n - 2, -1, -1):
            dp_b[i] = max(dp_b[i+1], max_p - prices[i])
            max_p = max(max_p, prices[i])
        
        # print(dp_f, dp_b)
        return max(dp_f[-1], max(dp_f[i] + dp_b[i + 1] for i in range(0, n - 1)))

空间优化：官方提供了一种空间复杂度为 O(1) 的解法：

买卖股票的最佳时机 III - 力扣官方题解

Python

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        buy1 = buy2 = prices[0]
        sell1 = sell2 = 0
        for i in range(1, n):
            buy1 = min(buy1, prices[i])
            sell1 = max(sell1, prices[i] - buy1)
            buy2 = min(buy2, prices[i] - sell1)
            sell2 = max(sell2, prices[i] - buy2)
        return sell2

---

LeetCode 0152 乘积最大子数组 (中等, 2022-01)

问题简述

给定整型数组，求乘积最大的非空连续子数组，返回乘积；

详细描述

给你一个整数数组 nums，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例 1:
    输入: [2,3,-2,4]
    输出: 6
    解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
    输入: [-2,0,-1]
    输出: 0
    解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-product-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：动态规划

• 延续连续子数组最大和的思路，定义 dp[i] 表示以 nums[i] 结尾的连续最大乘积；
• 区别在于非0值乘以负数时，最大值会变最小值，最小值变最大值；
• 因此可以考虑定义两个 dp：dp_max[i] 和 dp_min[i] 分别表示最大和最小乘积（详见代码）；
• 本题同样可以使用“滚动变量”的方式降低空间复杂度；

Python

class Solution:
    def maxProduct(self, nums: List[int]) -> int:

        ret = dp_max = dp_min = nums[0]
        for x in nums[1:]:
            tmp_mx = dp_max  # 临时变量
            dp_max = max(x, dp_max * x, dp_min * x)
            dp_min = min(x, dp_min * x, tmp_mx * x)
            ret = max(ret, dp_max)
        
        return ret

---

LeetCode 0198 打家劫舍 (中等, 2022-02)

问题简述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

198. 打家劫舍 - 力扣（LeetCode）

思路

• 定义 dfs(i) 表示前 i 家能打劫的最大价值；
• 【递归基】i <= 0 时，有 dfs(0) = 0；

  小细节：因为会用到 i-2 的状态，所以需要定义 i < 0 时的状态；

• 递推公式：dfs(i) = max(dfs(i-1), dfs(i-2) + nums[i-1])；

  对第 i 家（nums[i-1]），有两种可能，不抢（dfs(i-1)），抢（dfs(i-2) + nums[i-1]），去其中的较大值；

Python：递归

class Solution:
    def rob(self, nums: List[int]) -> int:

        from functools import lru_cache

        @lru_cache(maxsize=None)
        def dfs(i):
            if i == 0:  # 显然
                return 0
            if i == 1:  # 只有一家时，必抢
                return nums[0]
            
            r1 = dfs(i - 1)  # 不抢
            r2 = dfs(i - 2) + nums[i - 1]  # 抢
            return max(r1, r2)
        
        N = len(nums)
        return dfs(N)

Python：动态规划

class Solution:
    def rob(self, nums: List[int]) -> int:
        
        N = len(nums)
        dp = [0] * (N + 1)
        dp[1] = nums[0]

        for i in range(2, N + 1):
            r1 = dp[i - 1]  # 不抢
            r2 = dp[i - 2] + nums[i - 1]  # 抢
            dp[i] = max(r1, r2)

        return dp[-1]

---

LeetCode 0213 打家劫舍II (中等, 2022-02)

问题简述

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

213. 打家劫舍 II - 力扣（LeetCode）

思路

• 与打家劫舍的唯一区别就是不能同时偷首尾两家；
• 因此可以考虑分别计算 nums[1:] 和 nums[:-1]，求较大值；

  打家劫舍 II（动态规划，结构化思路，清晰题解） - Krahets

Python

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1: return nums[0]

        def f(nums):
            N = len(nums)
            dp = [0] * (N + 1)
            dp[1] = nums[0]

            for i in range(2, N + 1):
                dp[i] = max(dp[i-1], dp[i-2] + nums[i - 1])
            
            return dp[-1]
        
        return max(f(nums[1:]), f(nums[:-1]))

---

LeetCode 0300 最长递增子序列 (中等, 2022-01)

问题简述

给定整数数组 nums，返回最长严格递增子序列的长度；
进阶：
    你可以设计时间复杂度为 O(N^2) 的解决方案吗？
    你能把时间复杂度降到 O(NlogN) 吗?

详细描述

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：
    输入：nums = [10,9,2,5,3,7,101,18]
    输出：4
    解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
    输入：nums = [0,1,0,3,2,3]
    输出：4
示例 3：
    输入：nums = [7,7,7,7,7,7,7]
    输出：1

提示：
    1 <= nums.length <= 2500
    -104 <= nums[i] <= 104

进阶：
    你可以设计时间复杂度为 O(n2) 的解决方案吗？
    你能将算法的时间复杂度降低到 O(n log(n)) 吗?

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：动态规划

状态定义：dp[i] 表示以 nums[i] 结尾的最长递增子序列长度；

不能将 dp[i] 定义 nums[:i] 子数组中的最长递增子序列长度，虽然这样定义很直观，但它不满足最优子结构的条件，简单来说，就是你无法通过 dp[i-1] 得到 dp[i]。

Python

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        
        ret = 1
        dp = [1] * len(nums)
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:  # 如果要求非严格递增，将 '>' 改为 '>=' 即可
                    dp[i] = max(dp[i], dp[j] + 1)
            
            ret = max(ret, dp[i])
        
        return ret

思路2：优化 DP 的状态定义

• 考虑新的状态定义：dp[i] 表示长度为 i + 1 的最长递增子序列末尾的最小值；

  dp 序列一定时单调递增的，可用反证法证明，详见：最长递增子序列（动态规划 + 二分查找，清晰图解） - Krahets

  该怎么想出这个定义？——多看多做

• 是否满足最优子结构？
  • 即已知 dp[i - 1] 能否递推得到 dp[i] ；显然是可以的，当nums[i] > dp[i - 1]时，长度 +1，否则，长度不变；
• 如何更新dp？
  • 当 nums[i] > dp[i - 1] 时，直接添加到末尾；
  • 否则，要看是否需要更新 dp。根据 dp 递增的性质，找到 nums[i] 在 dp 中应该插入的位置，记 idx；比较 dp[idx] 与 nums[i] 的大小，如果 dp[idx] > nums[i] 根据定义，更新 dp[idx] = nums[i]；

从“贪心”角度来解释以上过程：如果我们要使上升子序列尽可能的长，则应该让序列上升得尽可能慢，即每次在上升子序列最后加上的那个数尽可能的小。

最长上升子序列 - 力扣官方题解

Python

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums: return 0

        # from bisect import bisect_left

        # 手写二分查找
        def bisect_left(ls, x):
            l, r = 0, len(ls)
            while l < r:
                m = (l + r) // 2
                if ls[m] < x:  # 注意这里要 <，如果是 <= 就是 bisect_right 了，不满足题意
                    l = m + 1
                else:
                    r = m
            return l

        dp = [nums[0]]  # dp[i] 表示长度为 (i+1) 的 LIS 的最后一个元素的最小值
        for x in nums[1:]:
            if x > dp[-1]:
                dp.append(x)
            else:
                idx = bisect_left(dp, x)  # 不能使用 bisect/bisect_right
                # if dp[idx] > x:
                #     dp[idx] = x
                dp[idx] = x  # 因为 bisect_left 返回的定义就是 dp[idx] <= x，所以可以直接赋值

        return len(dp)

---

LeetCode 0322 零钱兑换 (中等, 2022-02)

问题简述

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

322. 零钱兑换 - 力扣（LeetCode）

思路：完全背包

• 定义 dfs(a) 表示凑成金额 a 需要的最少硬币数；
• 递归基：1）显然 dfs(0) = 0；2）当 a 小于币值时，返回无穷大，表示无效结果；

Python：递归

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:

        from functools import lru_cache

        N = len(coins)

        @lru_cache(maxsize=None)
        def dfs(a):
            if a == 0: return 0
            if a < 0: return float('inf')

            ret = float('inf')
            for i in range(N):
                if a >= coins[i]:
                    ret = min(ret, dfs(a - coins[i]) + 1)
            return ret

        ret = dfs(amount)
        return -1 if ret == float('inf') else ret

Python：动态规划 写法1）根据递归过程改写

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:

        N = len(coins)
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0

        for a in range(1, amount + 1):
            for i in range(N):
                if a >= coins[i]:
                    dp[a] = min(dp[a], dp[a - coins[i]] + 1)
        
        return -1 if dp[-1] == float('inf') else dp[-1]

Python：动态规划 写法2）先遍历“物品”，在遍历“容量”

关于先后遍历两者的区别见完全背包 - 代码随想录，本题中没有区别；

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:

        N = len(coins)
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0

        for i in range(N):
            for a in range(coins[i], amount + 1):
                dp[a] = min(dp[a], dp[a - coins[i]] + 1)
        
        return -1 if dp[-1] == float('inf') else dp[-1]

---

LeetCode 0343 整数拆分 (中等, 2021-12)

问题简述

给定一个正整数 n，将其拆分为至少两个正整数的和，使这些整数的乘积最大化。返回最大乘积。

详细描述

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:
    输入: 2
    输出: 1
    解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
    输入: 10
    输出: 36
    解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/integer-break
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：动态规划

• 在不使用任何数学结论的前提下，可以把本题当做纯 DP 来做：

Python（写法1）

LeetCode 官方题解中的写法：整数拆分

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

        for i in range(2, n + 1):
            for j in range(1, i):
                # 状态定义：dp[i] 表示长度为 i 并拆分成至少两个正整数后的最大乘积（i>=1）
                #   j * (i - j)   表示将 i 拆分成 j 和 i-j，且 i-j 不再拆分
                #   j * dp[i - j] 表示将 i 拆分成 j 和 i-j，且 i-j 会继续拆分，dp[i-j] 即为继续拆分的最优结果（最优子结构）
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))

        return dp[n]

Python（写法2）

《剑指Offer》中的写法

class Solution:
    def cuttingRope(self, n: int) -> int:
        # 对于 n = 2、3 的情况，直接硬编码
        if n == 2:
            return 1
        if n == 3:
            return 2

        # 状态定义：dp[i] 表示长度为 i 并拆分成至少两个正整数后的最大乘积（i>3）
        #   当 i <= 3 时，不满足该定义，此时不拆效率最高
        #   初始状态（dp[0] 仅用于占位）
        dp = [0,1,2,3] + [0] * (n - 3) 

        for i in range(4, n + 1):
            for j in range(2, i):
                dp[i] = max(dp[i], dp[i-j] * dp[j])

        return dp[n]

思路2：数学/贪心

• 数学上可证：尽可能按长度为 3 切，如果剩余 4，则按 2、2 切；

  证明见：剪绳子1（数学推导 / 贪心思想，清晰图解）

• 简述：当 x >= 4 时，有 2(x-2) = 2x - 4 >= x；简言之，对任意大于等于 4 的因子，都可以拆成 2 和 x-2 而不损失性能；因此只需考虑拆成 2 或 3 两种情况（1除外）；而由于 2*2 > 3*1 和 3*3 > 2*2*2，可知最多使用两个 2；

Python

class Solution:
    def cuttingRope(self, n: int) -> int:
        import math
        if n <= 3:
            return n - 1
        
        a, b = n // 3, n % 3
        if b == 1:
            return int(math.pow(3, a - 1) * 4)
        elif b == 2:
            return int(math.pow(3, a) * 2)
        else:
            return int(math.pow(3, a))

---

LeetCode 0518 零钱兑换II (中等, 2022-02)

问题简述

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。 

518. 零钱兑换 II - 力扣（LeetCode）

思路1：递归

• 定义 dfs(a, i) 表示目标钱数为 a 且从第 i 种硬币开始取能得到的组合数；

  “从第 i 种硬币开始取”具体指第 i 种之后的硬币可以任意取，前面的 i-1 种不能取，详见代码；

• 递归基
  1. 规定 dfs(0,i) == 1；
  2. 隐含中止条件：当 coins[i] > j 时，dfs(a,i) == 0；

Python

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        from functools import lru_cache

        N = len(coins)

        @lru_cache(maxsize=None)
        def dfs(a, i):  # 目标钱数为 `a` 且从第 `i` 种硬币开始取能得到的组合数
            if a == 0: return 1

            ret = 0
            while i < N:
                if (x := coins[i]) <= a:
                    ret += dfs(a - x, i)
                i += 1

            return ret

        return dfs(amount, 0)

思路2：动态规划——基于完全背包的组合数问题

• 定义 dp[a] 表示构成目标值 i 的组合数；
• 转移方程 dp[a] += dp[a - coins[i]]，当 a >= coins[i] 时；
• 初始状态 dp[0] = 1；
• 关键点：先遍历“物品”（这里是硬币），在遍历“容量”（这里是金额）；

  关于先后遍历两者的区别见完全背包 - 代码随想录；

Python：动态规划

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        from functools import lru_cache

        N = len(coins)
        dp = [0] * (amount + 1)
        dp[0] = 1

        for i in range(N):
            x = coins[i]
            for j in range(x, amount + 1):
                dp[j] += dp[j - x]
        
        return dp[amount]

---

剑指Offer 1001 斐波那契数列 (简单, 2021-11)

问题简述

输入 n ，求斐波那契（Fibonacci）数列的第 n 项

详细描述

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
    F(0) = 0,   F(1) = 1
    F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：
    输入：n = 2
    输出：1
示例 2：
    输入：n = 5
    输出：5

提示：
    0 <= n <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

• 法1）递归
• 法2）DP（记忆化搜索），因为每个答案只与固定的前两个结果有关，因此可以使用滚动 DP；

Python：递归（会超时）

class Solution:
    
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return 1
        
        MAX = 1000000007
        return (self.fib(n-1) + self.fib(n-2)) % MAX

Python：动态规划

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

        dp = [0, 1]  # 因为每个答案只与固定的前两个结果有关，所以只需要“记忆”两个答案
        for _ in range(n - 1):
            dp[0], dp[1] = dp[1], dp[0] + dp[1]
        
        return dp[1] % MAX

---

剑指Offer 1001 斐波那契数列 (简单, 2021-11)

问题简述

输入 n ，求斐波那契（Fibonacci）数列的第 n 项

详细描述

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
    F(0) = 0,   F(1) = 1
    F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：
    输入：n = 2
    输出：1
示例 2：
    输入：n = 5
    输出：5

提示：
    0 <= n <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

• 法1）递归
• 法2）DP（记忆化搜索），因为每个答案只与固定的前两个结果有关，因此可以使用滚动 DP；

Python：递归（会超时）

class Solution:
    
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return 1
        
        MAX = 1000000007
        return (self.fib(n-1) + self.fib(n-2)) % MAX

Python：动态规划

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

        dp = [0, 1]  # 因为每个答案只与固定的前两个结果有关，所以只需要“记忆”两个答案
        for _ in range(n - 1):
            dp[0], dp[1] = dp[1], dp[0] + dp[1]
        
        return dp[1] % MAX

---

剑指Offer 1002 跳台阶 (简单, 2021-11)

问题简述

规定一次可以跳1级台阶或2级台阶。求跳上一个 n 级台阶总共有多少种跳法。

详细描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：
    输入：n = 2
    输出：2
示例 2：
    输入：n = 7
    输出：21
示例 3：
    输入：n = 0
    输出：1
提示：
    0 <= n <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

• 本题实际上就是求斐波那契数列，跳上 n 级台阶的方法数 f(n) = f(n-1) + f(n-2)，
• 只是初始状态不同，这里是 f(0) = 1, f(1) = 1；

Python：动态规划

class Solution:
    def numWays(self, n: int) -> int:
        MAX = 1000000007

        dp = [1, 1]  # 
        for _ in range(n - 1):
            dp[0], dp[1] = dp[1], dp[0] + dp[1]
        
        return dp[1] % MAX if n > 0 else dp[0]

---

剑指Offer 1401 剪绳子（整数拆分） (中等, 2021-11)

问题简述

给定一个正整数 n，将其拆分为至少两个正整数的和，使这些整数的乘积最大化。返回最大乘积。

详细描述

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

示例 1：
    输入: 2
    输出: 1
    解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
    输入: 10
    输出: 36
    解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：
    2 <= n <= 58

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jian-sheng-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：动态规划

• 在不使用任何数学结论的前提下，可以把本题当做纯 DP 来做：

Python（写法1）

LeetCode 官方题解中的写法：整数拆分

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

        for i in range(2, n + 1):
            for j in range(1, i):
                # 状态定义：dp[i] 表示长度为 i 并拆分成至少两个正整数后的最大乘积（i>=1）
                #   j * (i - j)   表示将 i 拆分成 j 和 i-j，且 i-j 不再拆分
                #   j * dp[i - j] 表示将 i 拆分成 j 和 i-j，且 i-j 会继续拆分，dp[i-j] 即为继续拆分的最优结果（最优子结构）
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))

        return dp[n]

Python（写法2，推荐）

《剑指Offer》中的写法

class Solution:
    def cuttingRope(self, n: int) -> int:
        # 对于 n = 2、3 的情况，直接硬编码
        if n == 2:
            return 1
        if n == 3:
            return 2

        # 状态定义：dp[i] 表示长度为 i 并拆分成至少两个正整数后的最大乘积（i>3）
        #   当 i <= 3 时，不满足该定义，此时不拆效率最高
        #   初始状态（dp[0] 仅用于占位）
        dp = [0,1,2,3] + [0] * (n - 3) 

        for i in range(4, n + 1):
            for j in range(2, i):
                dp[i] = max(dp[i], dp[i-j] * dp[j])

        return dp[n]

思路2：数学/贪心

• 数学上可证：尽可能按长度为 3 切，如果剩余 4，则按 2、2 切；

  证明见：剪绳子1（数学推导 / 贪心思想，清晰图解）

• 简述：当 x >= 4 时，有 2(x-2) = 2x - 4 >= x；简言之，对任意大于等于 4 的因子，都可以拆成 2 和 x-2 而不损失性能；因此只需考虑拆成 2 或 3 两种情况（1除外）；而由于 2*2 > 3*1 和 3*3 > 2*2*2，可知最多使用两个 2；

Python

class Solution:
    def cuttingRope(self, n: int) -> int:
        import math
        if n <= 3:
            return n - 1
        
        a, b = n // 3, n % 3
        if b == 1:
            return int(math.pow(3, a - 1) * 4)
        elif b == 2:
            return int(math.pow(3, a) * 2)
        else:
            return int(math.pow(3, a))

---

剑指Offer 1900 正则表达式匹配 (困难, 2021-11)

问题简述

请实现一个函数用来匹配包含'.'和'*'的正则表达式。

详细描述

请实现一个函数用来匹配包含'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

示例 1:
    输入:
    s = "aa"
    p = "a"
    输出: false
    解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
    输入:
    s = "aa"
    p = "a*"
    输出: true
    解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:
    输入:
    s = "ab"
    p = ".*"
    输出: true
    解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 4:
    输入:
    s = "aab"
    p = "c*a*b"
    输出: true
    解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5:
    输入:
    s = "mississippi"
    p = "mis*is*p*."
    输出: false
    s 可能为空，且只包含从 a-z 的小写字母。
    p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：动态规划

正则表达式匹配（动态规划，清晰图解） - Krahets

• 记主串为 s，模式串为 p；
• 将 s 的前 i 个 字符记为 s[:i]，p 的前 j 个字符记为 p[:j]；
• 整体思路是从 s[:1] 和 p[:1] 开始，判断 s[:i] 和 p[:j] 能否匹配；

Python

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)

        # dp[i][j] := 代表字符串 s 的前 i 个字符和 p 的前 j 个字符能否匹配
        dp = [[False] * (n + 1) for _ in range(m + 1)]

        dp[0][0] = True  # ‘空主串’与‘空模式串’匹配

        # 初始化首行：‘空主串’与‘特殊模式串’匹配（如 a*、a*b* 等）
        for j in range(2, n + 1, 2):
            dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'

        # 状态转移
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                # 便于理解，记 s[I] == s[i - 1] 表示 s 的第 i 个字符，p[J] 同理
                I, J = i - 1, j - 1
                # 根据 p 的 第 j 个字符是否为 *，分两种情况讨论
                if p[J] != '*':
                    # s[:i-1] 与 p[:j-1] 匹配的前提下，‘s 的第 i 个字符 == p 的第 j 个字符’ 或 ‘p 的第 j 个字符是 .’
                    #   这里 s[i-1] 和 p[j-1] 分别表示的是 s 和 p 的第 i 个和第 j 个字符
                    if dp[i - 1][j - 1] and (s[I] == p[J] or p[J] == '.'):
                        dp[i][j] = True
                else:  # 当 p[J] == '*' 时
                    # 情况1：* 匹配了 0 个字符，如 'a' 和 'ab*'
                    if dp[i][j - 2]:
                        dp[i][j] = True
                    # 情况2：* 匹配了至少一个字符，如 'ab' 和 'ab*'
                    #   dp[i - 1][j] == True 表示在 '[a]b' 和 '[ab*]' 中括号部分匹配的前提下，
                    #   再看 s[I] 与 p[J-1] 是否相同，或者 p[J-1] 是否为 .
                    elif dp[i - 1][j] and (s[I] == p[J - 1] or p[J - 1] == '.'):
                        dp[i][j] = True

        return dp[m][n]

思路2：递归

• 看到一份非常简洁的递归代码；

  见正则表达式匹配（动态规划，清晰图解） - 评论区

C++

class Solution {
public:
    bool isMatch(string s, string p) 
    {
        if (p.empty()) 
            return s.empty();
        
        bool first_match = !s.empty() && (s[0] == p[0] || p[0] == '.');
        
        // *前字符重复>=1次 || *前字符重复0次（不出现）
        if (p.size() >= 2 && p[1] == '*')  
            return (first_match && isMatch(s.substr(1), p)) || isMatch(s, p.substr(2));
        else  // 不是*，减去已经匹配成功的头部，继续比较
            return first_match && isMatch(s.substr(1), p.substr(1));    
    }
};

---

剑指Offer 4200 连续子数组的最大和 (简单, 2021-12)

问题简述

给定一个整型数组，求其连续子数组的最大和。

详细描述

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例1:
    输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
    输出: 6
    解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

提示：
    1 <= arr.length <= 10^5
    -100 <= arr[i] <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：动态规划

• 状态定义：记 dp[i] 表示以 nums[i] 结尾的连续子数组最大和；

  “以 nums[i] 结尾”表示就是这个数一定会加上去，那么要看的就是这个数前面的部分要不要加上去——大于零就加，小于零就舍弃。

• 转移方程：
  • 当 $dp[i-1] > 0$ 时：执行 $dp[i] = dp[i-1] + nums[i]$；
  • 当 $dp[i-1] \le 0$ 时：执行 $dp[i] = nums[i]$；

Python

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:

        n = len(nums)
        dp = [float('-inf')] * n

        dp[0] = nums[0]
        for i in range(1, n):
            dp[i] = max(nums[i], dp[i-1] + nums[i])
        
        return max(dp)

优化：因为每次只与上一个状态有关，所以可以只使用一个变量来存储；

Python：空间优化

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:

        ret = dp = nums[0]
        for x in nums[1:]:
            dp = max(dp + x, x)
            ret = max(dp, ret)
        
        return ret

---

剑指Offer 4600 斐波那契数列-3（把数字翻译成字符串） (中等, 2021-12)

问题简述

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。求一个数字有多少种不同的翻译方法。

详细描述

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例 1:
    输入: 12258
    输出: 5
    解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

提示：
    0 <= num < 231

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：动态规划

• 首先要意识到本题是一个有条件的斐波那契数列/跳台阶问题；
  • 假设不是26个字母，而是100个不同的字母，那么是不是 dp[i] = dp[i-1] + dp[i-2]？；
• 因此本题另一个考察点就是如何实现这个条件判断；

Python

import math


class Solution:
    def translateNum(self, num: int) -> int:

        # num 的位数
        N = int(math.log10(num)) + 1 if num > 0 else 1

        def slide(i):
            """截取 num 中的两位数，效果如下
            Examples:
                >>> slide(54321, 1)
                54
                >>> slide(54321, 2)
                43
                >>> slide(54321, 3)
                32
            """
            return num // 10 ** (N - i - 1) % 100

        dp0 = 1
        dp1 = 2 if slide(1) < 26 else 1

        if N == 1:
            return dp0
        if N == 2:
            return dp1

        for i in range(2, N):
            if 9 < slide(i) < 26:  # “01” 不能翻译成 “a”，所以要大于 9
                dp0, dp1 = dp1, dp0 + dp1
            else:
                dp0, dp1 = dp1, dp1

        return dp1

---

剑指Offer 4700 礼物的最大价值 (中等, 2021-12)

问题简述

给定 m*n 的整型数组 grid，求从左上角到右下角路线中和的最大值（每次向下或向右移动一格）

示例输入: 
    [1,3,1]
    [1,5,1]
    [4,2,1]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

详细描述

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

示例 1:
    输入: 
    [
      [1,3,1],
      [1,5,1],
      [4,2,1]
    ]
    输出: 12
    解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
 
提示：
    0 < grid.length <= 200
    0 < grid[0].length <= 200

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：动态规划

状态定义

• 记 dp[i][j] := 从左上角走至 (i,j) 位置时的最大值

转移方程

• dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]

初始状态

• dp[i][0] = sum(grid[:i][0])
• dp[0][j] = sum(grid[0][:j])

Python：本地修改

因为 dp[i][j] 只与 dp[i-1][j] 和 dp[i][j-1] 有关，因此可以直接将 grid 作为 dp 矩阵，原地修改；

题解：礼物的最大价值（动态规划，清晰图解）

class Solution:
    def maxValue(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        # 初始化
        for j in range(1, n): 
            grid[0][j] += grid[0][j - 1]
        for i in range(1, m):
            grid[i][0] += grid[i - 1][0]
        
        for i in range(1, m):
            for j in range(1, n):
                grid[i][j] += max(grid[i][j - 1], grid[i - 1][j])

        return grid[-1][-1]

Python：非本地修改，优化空间复杂度

因为不存在回溯（每次只能向下或向右），所以只需要保存上一行（或上一列）的结果即可；

状态定义

• 记 dp[j] := 从左上角走至 (i,j) 位置时的最大值

转移方程

• dp[j] = max(dp[j-1], dp[j]) + grid[i][j]

  dp[j-1] + grid[i][j] 表示路线为 grid[i-1][j-1] → grid[i-1][j] → grid[i][j]，即先往右再向下
  dp[j]   + grid[i][j] 表示路线为 grid[i-1][j-1] → grid[i][j-1] → grid[i][j]，即先向下再往右
  然后选择这两条路线中较大的更新 dp[j]
  

初始状态

• dp[j] = sum(grid[0][:j])

class Solution:
    def maxValue(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]: return 0

        m, n = len(grid), len(grid[0])

        # 初始化第一行的结果
        dp = [grid[0][0]] + [0] * (n - 1)
        for i in range(1, n):
            dp[i] = dp[i - 1] + grid[0][i]

        for i in range(1, m):
            dp[0] = dp[0] + grid[i][0]
            for j in range(1, n):
                # dp[j-1] + grid[i][j] 表示 grid[i-1][j-1] → grid[i][j-1] → grid[i][j]
                # dp[j]   + grid[i][j] 表示 grid[i-1][j-1] → grid[i-1][j] → grid[i][j]
                # 然后选择这两条路线中较大的更新 dp[j]
                dp[j] = max(dp[j-1], dp[j]) + grid[i][j]
        
        return dp[n-1]

---

剑指Offer 4800 最长不含重复字符的子字符串 (中等, 2021-12)

问题简述

求字符串 s 中的最长不重复子串，返回其长度；

详细描述

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例 1:
    输入: "abcabcbb"
    输出: 3 
    解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
    输入: "bbbbb"
    输出: 1
    解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
    输入: "pwwkew"
    输出: 3
    解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
        请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 
提示：
    s.length <= 40000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：双指针（推荐）

• 双指针同向遍历每个字符；同时使用哈希表记录每个字符的最新位置；
• 如果右指针遇到已经出现过的字符，则将左指针移动到该字符的位置，更新最大长度；
• 具体细节见代码；

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s: return 0
        
        c2p = dict()
        lo = -1  # 左指针
        ret = 1
        for hi, c in enumerate(s):  # 遍历右指针
            if c not in c2p or c2p[c] < lo:  # 如果当前字符还没有出现过，或者出现过但是在左指针的左侧，可以更新最大长度
                ret = max(ret, hi - lo)
            else:  # 否则更新左指针
                lo = c2p[c]

            c2p[c] = hi  # 更新字符最新位置

        return ret

思路2：动态规划

[最长不含重复字符的子字符串（动态规划 / 双指针 + 哈希表，清晰图解）](https://

状态定义 leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/solution/mian-shi-ti-48-zui-chang-bu-han-zhong-fu-zi-fu-d-9/)

• 记 dp[i] := 以第 i 个字符为结尾的不含重复字符的子串的最大长度；

转移方程

dp[i] = dp[i-1] + 1     if dp[i-1] < i-i
      = i-j             else

其中 j 表示字符 s[i] 上一次出现的位置；

• 使用一个 hash 表记录每个字符上一次出现的位置；
• 因为当前状态只与上一个状态有关，因此可以使用一个变量代替数组（滚动）；

初始状态

• dp[0] = 1

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        idx = dict()
        ret = dp = 0
        for i, c in enumerate(s):
            if c not in idx:
                dp = dp + 1
            else:
                j = idx[c]  # 如果 c 已经出现过，获取其上一个出现的位置
                if dp < i - j:  # 参考双指针思路，这里相当于上一次出现的位置在左指针之前，不影响更新长度
                    dp = dp + 1
                else:  # 反之，在左指针之后
                    dp = i - j

            idx[c] = i  # 更新位置 i
            ret = max(ret, dp)  # 更新最大长度
        return ret

---

剑指Offer 4900 丑数 (中等, 2021-12)

问题简述

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。
求按从小到大的顺序的第 n 个丑数。

详细描述

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例:
    输入: n = 10
    输出: 12
    解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
    1 是丑数。
    n 不超过1690。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/chou-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：暴力解

• 根据丑数的定义，有如下推论：
  • 一个丑数乘以 2、3、5 之后，还是丑数；
  • 从 1 开始，对每个丑数都乘以 2、3、5，再加入丑数序列（移除重复），那么不会产生遗漏；
• 对已有的丑数乘以 2、3、5，取其中大于已知最大丑数的最小值；

Python

class Solution:
    def nthUglyNumber(self, n: int) -> int:

        dp = [1]
        for i in range(1, n):
            M = dp[-1]  # 当前最大丑数

            tmp = []
            for x in dp[::-1]:  # 逆序遍历
                if x * 5 < M:
                    break
                    
                if x * 2 > M:
                    tmp.append(x * 2)
                if x * 3 > M:
                    tmp.append(x * 3)
                if x * 5 > M:
                    tmp.append(x * 5)

            dp.append(min(tmp))

        return dp[-1]

思路：动态规划

• 暴力解中存在大量重复计算，可以考虑动态规划；

Python

• 代码解读：丑数，清晰的推导思路

class Solution:
    def nthUglyNumber(self, n: int) -> int:

        dp = [1] * n
        p1, p2, p3 = 0, 0, 0  # 三指针归并

        for i in range(1, n):
            n2, n3, n5 = dp[p1] * 2, dp[p2] * 3, dp[p3] * 5
            dp[i] = min(n2, n3, n5)

            # 去重：使用 if 而不是 elif
            if dp[i] == n2:
                p1 += 1
            if dp[i] == n3:
                p2 += 1
            if dp[i] == n5:
                p3 += 1

        return dp[-1]

---

剑指Offer 6000 n个骰子的点数 (中等, 2022-01)

问题简述

把 n 个骰子扔在地上，所有骰子朝上一面的点数之和为 s。
输入 n，打印出 s 的所有可能的值出现的概率（按 s 从小到大排列）。

详细描述

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

示例 1:
    输入: 1
    输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
示例 2:
    输入: 2
    输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]

限制：
    1 <= n <= 11

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：从暴力递归到动态规划

• 定义 dfs(k) 返回 k 个骰子产生的可能性序列 dp，其中 dp[i] 表示 k 个骰子掷出点数 i 的可能数；
• 【递归基】k=1 时，dfs(1) 返回 dp = [_, 1, 1, 1, 1, 1, 1]（为方便编码，dp[:n] 为占位符，无实际意义）
• 递归过程即使用 dfs(k-1) 返回的 dp_pre 生成 dfs(k) 的 dp；
• 然后根据暴力递归过程直接写出动态规划的代码（已经与原问题解耦）；

Python：暴力递归

class Solution:
    def dicesProbability(self, n: int) -> List[float]:

        def dfs(k):
            if k == 1:
                return [1] * 7

            dp_pre = dfs(k - 1)
            dp = [0] * (k * 6 + 1)

            # 遍历方式 1:
            # for i in range(1 * (n - 1), 6 * (n - 1) + 1):  # n - 1 个骰子的点数范围
            #     for d in range(1, 7):  # 当前骰子掷出的点数
            #         dp[i + d] += dp_pre[i]

            # 遍历方式 2（推荐，不需要判断范围）：
            for i in range(1 * k, 6 * k + 1):  # n 个骰子的点数范围
                for d in range(1, 7):  # 当前骰子掷出的点数
                    if 1 * (k - 1) <= i - d <= 6 * (k - 1):
                        dp[i] += dp_pre[i - d]

            return dp

        dp = dfs(n)
        return [x / (6 ** n) for x in dp[n:]]

Python：动态规划

class Solution:
    def dicesProbability(self, n: int) -> List[float]:
        

        dp = [1] * 7

        for k in range(2, n + 1):
            dp_pre = dp
            dp = [0] * (k * 6 + 1)
            for i in range(1 * k, 6 * k + 1):  # n 个骰子的点数范围
                for d in range(1, 7):  # 当前骰子掷出的点数
                    if 1 * (k - 1) <= i - d <= 6 * (k - 1):
                        dp[i] += dp_pre[i - d]

        return [x / (6 ** n) for x in dp[n:]]

思路2：从“跳台阶”理解本题

• “跳台阶”的递推公式为：dp[i] = dp[i-1] + dp[i-2]；
• 在本题中，可以看做目标台阶数为 i，每次可以跳 1~6 步；对 k 个骰子，i 的范围为 k ~ 6*k，每次都是从 n-1 个骰子的可能性出发；
• 因此本题的递推公式为：dp[k][i] = dp[k-1][i-1] + dp[k-1][i-2] + .. + dp[k-1][i-6]；
  • 同时因为每一轮只和上一轮相关，可以使用两个数组滚动优化空间；

    也可以只是用一个数组，参考：n个骰子的点数 - 路漫漫我不畏

• 代码同上。

---

剑指Offer 6200 圆圈中最后剩下的数字（约瑟夫环问题） (中等, 2022-01)

问题简述

0 ~ n-1 这 n 个数字围成一个圆圈，从数字0开始，每次从这个圆圈里删除第 m 个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

详细描述

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

示例 1：
    输入: n = 5, m = 3
    输出: 3
示例 2：
    输入: n = 10, m = 17
    输出: 2

限制：
    1 <= n <= 10^5
    1 <= m <= 10^6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：暴力解（超时）

Python

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:

        nums = list(range(n))
        idx = 0
        while len(nums) > 1:
            idx = (idx + m - 1) % len(nums)
            nums.pop(idx)
        
        return nums[0]

思路2：递推

• 虽然我们不知道这个最终的值是哪个，但是可以确定的是在最后一轮删除后，这个值在数组中的索引一定是 0（此时数组中只有一个值了）；
• 递推的目的就是每次还原这个值在上一轮所在的索引，直到第一轮，然后就可以根据索引从数组中找到这个值了；
• 记 f(i) 表示倒数第 i 轮时目标值所在的索引（i>=1），显然有 f(1) = 0；
• 递推公式：f(i) = (f(i-1) + m) % i（倒数第 i 轮，数组的长度也为 i，所以是对 i 取余）
  • (f(i-1) + m) % i
• 关于递推公式的具体解析可以参`考「换个角度举例解决约瑟夫环」

Python

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:

        # nums = list(range(n))  # 因为 nums = [0..n-1]

        idx = 0  # 因为最后一轮数组中只有一个值了，所以此时目标的索引一定是 0
        for i in range(2, n + 1):
            idx = (idx + m) % i  # 倒数第 i 轮时目标的索引
        
        # return nums[idx]
        return idx  # 因为 nums = [0..n-1]，所以 nums[idx] == idx

---

牛客 0017 最长回文子串 (中等, 2022-01)

问题简述

求给定字符串中最长回文子串的长度。

最长回文子串_牛客题霸_牛客网

思路1：模拟中心扩散（推荐）

• 中心扩散直观，且不需要额外的空间，比动态规划的方法更好；

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param A string字符串 
# @return int整型
#
class Solution:
    def getLongestPalindrome(self , A: str) -> int:
        # write code here
        n = len(A)
        
        def process(l, r):
            tmp = 1  # 使用一个变量保存已知的最大长度
            while l >= 0 and r < n:
                if A[l] != A[r]:
                    break
                tmp = r - l + 1
                l -= 1
                r += 1
            # return r - l + 1  # 直接返回有问题，无法判断最后一次是否匹配上
            return tmp
        
        ret = 1
        for i in range(len(A) - 1):
            # 同时处理 process(i, i), process(i, i + 1) 避免奇偶的讨论
            ret = max(ret, process(i, i), process(i, i + 1))
            
        return ret

思路2：动态规划

• DP 虽然能解，但是不够直观，且初始状态容易写错（相邻两个字符相同的情况）；

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param A string字符串 
# @return int整型
#
class Solution:
    def getLongestPalindrome(self , A: str) -> int:
        # write code here
        n = len(A)
        dp = [[0] * n for _ in range(n)]

        for i in range(n):
            dp[i][i] = 1
        
        start = 0
        length = 1
        for j in range(1, n):  # 子串的结束位置
            for i in range(j - 1, -1, -1):  # 子串的开始位置
                if i == j - 1:
                    dp[i][j] = 1 if A[i] == A[j] else 0
                else:
                    dp[i][j] = 1 if dp[i + 1][j - 1] and A[i] == A[j] else 0

                if dp[i][j]:
                    if j - i + 1 > length:
                        length = j - i + 1
                        start = i

        return length

---

牛客 0019 连续子数组的最大和 (简单, 2022-01)

问题简述

给定数组 arr，求其连续子数组的最大和。

连续子数组的最大和_牛客题霸_牛客网

思路：动态规划

• 记 dp[i] 表示以 arr[i] 结尾的最大和；
• 则 dp[i] = max(dp[i - 1] + arr[i], arr[i])；
• 因为 dp[i] 只与上一个状态有关，因此可以使用滚动变量优化（详见代码）；

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param array int整型一维数组 
# @return int整型
#
class Solution:
    def FindGreatestSumOfSubArray(self , array: List[int]) -> int:
        # write code here
        ret = dp = array[0]
        for x in array[1:]:
            dp = max(x, dp + x)
            ret = max(ret, dp)
        
        return ret

---

牛客 0034 求路径 (简单, 2022-02)

问题简述

一个机器人在m×n大小的地图的左上角（起点）。
机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。
可以有多少种不同的路径从起点走到终点？

求路径_牛客题霸_牛客网

思路：动态规矩

Python：递归

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param m int整型 
# @param n int整型 
# @return int整型
#
class Solution:
    def uniquePaths(self , m: int, n: int) -> int:
        # write code here
        from functools import lru_cache
        
        @lru_cache(maxsize=None)
        def dp(i, j):
            if i == m and j == n:
                return 1
            if i > m or j > n: return 0
            
            return dp(i + 1, j) + dp(i, j + 1)
        
        return dp(1, 1)

---

牛客 0035 编辑距离(二) (较难, 2022-02)

问题简述

给定两个字符串str1和str2，再给定三个整数ic，dc和rc，分别代表插入、删除和替换一个字符的代价，请输出将str1编辑成str2的最小代价。

编辑距离(二)_牛客题霸_牛客网

思路：动态规划

• 定义 dp(i, j) 表示将 s1[:i] 编辑到 s2[:j] 的最小代价；

写法1：递归

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# min edit cost
# @param str1 string字符串 the string
# @param str2 string字符串 the string
# @param ic int整型 insert cost
# @param dc int整型 delete cost
# @param rc int整型 replace cost
# @return int整型
#
class Solution:
    def minEditCost(self , str1: str, str2: str, ic: int, dc: int, rc: int) -> int:
        # write code here
        import sys
        sys.setrecursionlimit(10000)
        
        from functools import lru_cache
        
        @lru_cache(maxsize=None)
        def dp(i, j):
            if i == 0 and j == 0: return 0
            if i == 0: return ic * j
            if j == 0: return dc * i
            
            r1 = dp(i - 1, j) + dc
            r2 = dp(i, j - 1) + ic
            r3 = dp(i - 1, j - 1)
            if str1[i - 1] != str2[j - 1]:
                r3 += rc
            
            return min(r1, r2, r3)
        
        return dp(len(str1), len(str2))

优化：可以看到，想让递归代码通过所有用例，需要解除递归深度限制，还有用上记忆化搜素；下面是把递归代码一比一修改为标准动态规划写法的代码；

写法2：动态规划

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# min edit cost
# @param str1 string字符串 the string
# @param str2 string字符串 the string
# @param ic int整型 insert cost
# @param dc int整型 delete cost
# @param rc int整型 replace cost
# @return int整型
#
class Solution:
    def minEditCost(self , str1: str, str2: str, ic: int, dc: int, rc: int) -> int:
        # write code here
        
        m, n = len(str1), len(str2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(m + 1):
            for j in range(n + 1):
                if i == 0: 
                    dp[i][j] = ic * j
                    continue
                if j == 0: 
                    dp[i][j] = dc * i
                    continue
                r1 = dp[i - 1][j] + dc
                r2 = dp[i][j - 1] + ic
                r3 = dp[i - 1][j - 1]
                if str1[i - 1] != str2[j - 1]:
                    r3 += rc
                dp[i][j] = min(r1, r2, r3)
        
        return dp[-1][-1]

---

牛客 0059 矩阵的最小路径和 (中等, 2022-03)

问题简述

给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

矩阵的最小路径和_牛客题霸_牛客网

思路

• 定义 dp(i,j) 表示到达 m[i][j] 最短距离；
• 递推公式：dp(i,j) = m[i][j] + min(dp(i-1,j), dp(i,j-1))；
• 初始化：
  • dp(i,0)=sum(m[:i][]0)
  • dp(0,j)=sum(m[0][:j])；

递归写法

class Solution:
    def minPathSum(self, matrix: List[List[int]]) -> int:
        
        import sys
        sys.setrecursionlimit(100000)
        from functools import lru_cache
        
        @lru_cache(maxsize=None)
        def dfs(i, j):
            if i == 0 and j == 0: return matrix[i][j]
            if i == 0: return sum(matrix[i][j] for j in range(j + 1))
            if j == 0: return sum(matrix[i][j] for i in range(i + 1))
            
            return matrix[i][j] + min(dfs(i - 1, j), dfs(i, j - 1))
        
        m, n = len(matrix), len(matrix[0])
        return dfs(m - 1, n - 1)

迭代写法（略）

---

牛客 0065 斐波那契数列 (入门, 2022-03)

问题简述

略

斐波那契数列_牛客题霸_牛客网

思路

• dp(i) := dp(i-1) + dp(i-1)

Python

class Solution:
    def Fibonacci(self , n: int) -> int:
        
        from functools import lru_cache
        
        @lru_cache(maxsize=None)
        def dp(i):
            if i in (1, 2): return 1
            
            return dp(i - 1) + dp(i - 2)
        
        return dp(n)

---

牛客 0068 跳台阶 (简单, 2022-03)

问题简述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

跳台阶_牛客题霸_牛客网

思路

• dp(i) := dp(i-1) + dp(i-2)

Python

class Solution:
    def jumpFloor(self , n: int) -> int:
        
        from functools import lru_cache
        
        @lru_cache(maxsize=None)
        def dp(i):
            if i == 1: return 1
            if i == 2: return 2
            
            return dp(i - 1) + dp(i - 2)
        
        return dp(n)

---

牛客 0091 最长上升子序列(三) (较难, 2022-03)

问题简述

给定数组，返回字典序最小的最长上升子序列；

最长上升子序列(三)_牛客题霸_牛客网

思路：动态规划

• 为了返回字典序最小的 LIS，本题需要结合两种 DP 状态；
  • 记 dp_end[i] 表示长度为 (i+1) 的 LIS 结尾的最小值；
  • 记 dp_len[i] 表示以 arr[i] 结尾的 LIS 的长度；

  这两种状态都可以用来求 LIS 的长度，前者的时间复杂度为 $O(n\log n)$，后者为 $O(n^2)$

• 得到这两个状态序列后就可以来计算具体的 LIS 了；下面举例说明如何使用这两个状态来还原 LIS；

  arr:    [1,2,8,6,4]
  dp_len: [1,2,3,3,3]
  dp_end: [1,2,4]
  # 这里省略了这两个状态序列的生成过程，
  # 因为 dp_len 可以在计算 dp_end 的过程中一起获得，因此时间复杂度依然是 `O(NlogN)`
  
  初始化：
      cnt = len(dp_end) # LIS 的长度
      ret = [0] * cnt  # 记录 LIS
  
  然后逆序遍历 dp_len
  当 dp_len[i] == cnt 时，将 ret[cnt - 1] 赋值为 arr[i]，同时 cnt -= 1
  
  为什么要逆序遍历？
      举个例子，arr 结尾的三个数，其最大的 LIS 长度都是 3，但其中 4 是最小的，
      因为如果它不是最小的，意味着它对应的 LIS 长度就应该大于 3 了
  

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# retrun the longest increasing subsequence
# @param arr int整型一维数组 the array
# @return int整型一维数组
#
class Solution:
    def LIS(self, arr: List[int]) -> List[int]:
        # write code here
        if not arr: return []

        from bisect import bisect_left

        dp_end = [arr[0]]  # dp_end[i] 表示长度为 (i+1) 的 LIS 结尾的最小值
        dp_len = [1]  # dp_len[i] 表示以 arr[i] 结尾的 LIS 的长度
        for x in arr[1:]:
            if x > dp_end[-1]:
                dp_end.append(x)
                dp_len.append(len(dp_end))
            else:
                idx = bisect_left(dp_end, x)
                dp_end[idx] = x
                dp_len.append(idx + 1)

        cnt = len(dp_end)
        ret = [0] * cnt
        for i in range(len(arr) - 1, -1, -1):
            if dp_len[i] == cnt:
                cnt -= 1
                ret[cnt] = arr[i]
        
        return ret

---

牛客 0127 最长公共子串 (中等, 2022-03)

问题简述

给定两个字符串str1和str2,输出两个字符串的最长公共子串
题目保证str1和str2的最长公共子串存在且唯一。 

最长公共子串_牛客题霸_牛客网

思路1：动态规划（超时）

• 定义 dp(i, j) 表示以 s1[i - 1] 和 s2[j - 1] 结尾的最长公共子串；
  • 注意：dp(i, j) 保存的并不是全局最优解，所以需要用全局变量来动态更新；
  • 本题中，因为需要返回具体子串，所以可以保存两个变量，一个是结尾索引，一个是子串长度，根据这两个变量就可以找到具体的公共子串；
• 初始化 i == 0 or j == 0 时，dp(i, j) == 0
• 转移方程：dp(i, j) = dp(i - 1, j - 1) + 1 if s1[i - 1] == s2[j - 1] else 0；
  • 值得注意的是，当前状态 (i, j) 只跟 (i-1, j-1) 状态有关，这与常见的双样本位置对应模型不同（比如“编辑距离”）；
  • 具体来说，状态转移时没有用到 (i, j-1) 和 (i-1, j)，但它们依然是要计算的，这在迭代写法中是自然的；但是在递归写法中很容易被忽略（因为转移方程中没有它们），详见递归写法的代码；

写法1）递归

class Solution:
    def LCS(self , s1: str, s2: str) -> str:
        # write code here
        import sys
        sys.setrecursionlimit(100000)
        from functools import lru_cache
        
        self.mLen = 0
        self.end = 0
        
        @lru_cache(maxsize=None)
        def dp(i, j):
            if i == 0 or j == 0: return 0
            # 可以省略
            # if i == 1: return int(s1[0] == s2[j - 1])
            # if j == 1: return int(s1[i - 1] == s2[0])

            # 虽然没有用到这两个状态的值，但依然要调用，这是递归写法很容易忽略的点
            _ = dp(i - 1, j)
            _ = dp(i, j - 1)
            r = dp(i - 1, j - 1) + 1 if s1[i - 1] == s2[j - 1] else 0
            # 更新全局最优解
            if r > self.mLen:
                self.mLen = r
                self.end = i
            return r
        
        dp(len(s1), len(s2))
        return s1[self.end - self.mLen: self.end]

写法2）迭代（从递归修改而来）

class Solution:
    def LCS(self , s1: str, s2: str) -> str:
        
        mLen = 0
        end = 0
        m, n = len(s1), len(s2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                # 可以省略
                # if i == 0 or j == 0:
                #     dp[i][j] = 0
                dp[i][j] = dp[i - 1][j - 1] + 1 if s1[i - 1] == s2[j - 1] else 0
                if dp[i][j] > mLen:
                    mLen = dp[i][j]
                    end = i

        return s1[end - mLen: end]

思路2

• 有一个超长用例导致上面的代码超时；
• 下面是另一种实现方式，本质上跟动态规划的思路是一样的；

Python

class Solution:
    def LCS(self , s1: str, s2: str) -> str:
        
        ret = ''
        mLen = 0
        
        for i in range(len(s1)):  # 遍历每一个 s1[:i + 1] 子串
            sub = s1[i - mLen: i + 1]  # 截取可能的最长公共子串
            if sub in s2:  # 如果是公共子串
                ret = sub  # 保存结果
                mLen += 1  # 尝试更长的子串
        
        return ret

---

牛客 0145 01背包 (中等, 2022-03)

问题简述

给定最多能容纳 V 体积的背包，和 n 个物品，每个物品有重量(w)和体积(v)两个属性；
求背包能放的最大重量；
每个物品的重量(w)和体积(v)保存在数组 vw 中；

示例1：
    输入：10,2,[[1,3],[10,4]]
    返回：4
示例2：
    输入：10,2,[[1,3],[9,8]]
    返回：11

01背包_牛客题霸_牛客网

总结

• 熟练掌握思路 1 的优化路径（解新题）；
• 牢记 01 背包的一维转移方程：
  • 优化目标是最大重量：dp[i] = max(dp[i], dp[i - v[i]] + w[i])
  • 优化目标是最小空间：dp[i] = min(dp[i], dp[i - w[i]] + v[i])

思路1：暴力递归+记忆化搜索 -> 动态规划

Python：写法1）暴力递归+记忆化搜索

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算01背包问题的结果
# @param V int整型 背包的体积
# @param n int整型 物品的个数
# @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
# @return int整型
#
class Solution:
    def knapsack(self , V: int, n: int, vw: List[List[int]]) -> int:
        # write code here
        import sys
        sys.setrecursionlimit(1010)  # 解除递归深度限制
        
        # 记忆空间
        dp = dict()
        
        # 剩余空间为 rest 的情况下，前 i 个物品能装载的最大值
        def dfs(i, rest):
            if (i, rest) in dp:
                return dp[(i, rest)]
            
            # 递归基
            if i == 0:
                return 0
            
            # 不拿第 i 个物品
            r1 = dfs(i - 1, rest)
            # 拿第 i 个物品，前提是空间足够
            r2 = 0
            if rest >= vw[i - 1][0]:  # 注意第 i 个物品第下标是 i-1，这里最容易犯错
                r2 = dfs(i - 1, rest - vw[i - 1][0]) + vw[i - 1][1]
            
            # 记忆
            dp[(i, rest)] = max(r1, r2)
            return dp[(i, rest)]
        
        return dfs(n, V)  # 因为下标从 0 开始，所以第 n 个物品的下标为 n-1

Python：写法2）使用标准库提供的缓存（爆栈）

• 不知道什么原因无法通过最长的用例，好像 lru_cache 和 setrecursionlimit 不能同时生效；

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算01背包问题的结果
# @param V int整型 背包的体积
# @param n int整型 物品的个数
# @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
# @return int整型
#
class Solution:
    def knapsack(self , V: int, n: int, vw: List[List[int]]) -> int:
        # write code here
        from functools import lru_cache
        import sys
        sys.setrecursionlimit(1010)  # 解除递归深度限制
        
        # 剩余空间为 rest 的情况下，前 i 个物品能装载的最大值
        @lru_cache(maxsize=None)
        def dfs(i, rest):
            if i == -1:  # 因为下标从 0 开始，所以递归基设为 -1
                return 0
            
            # 不拿第 i 个物品
            r1 = dfs(i - 1, rest)
            # 拿第 i 个物品，前提是空间足够
            r2 = 0 if rest < vw[i][0] else dfs(i - 1, rest - vw[i][0]) + vw[i][1]

            return max(r1, r2)
        
        return dfs(n - 1, V)  # 因为下标从 0 开始，所以第 n 个物品的下标为 n-1

Python：写法3）将暴力递归转成动态规划

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算01背包问题的结果
# @param V int整型 背包的体积
# @param n int整型 物品的个数
# @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
# @return int整型
#
class Solution:
    def knapsack(self , V: int, n: int, vw: List[List[int]]) -> int:
        # write code here
        
        dp = [[0] * (V + 1) for _ in range(n + 1)]
        # 对应递归基：剩余容量为 V 时前 0 个物品的最大重量
        dp[0][V] = 0
        
        for i in range(1, n + 1):
            for rest in range(V + 1):  # 这里正序逆序遍历都可以
                # 与 dfs 的过程一一对应
                r1 = dp[i - 1][rest]
                r2 = 0
                if rest >= vw[i - 1][0]:
                    r2 = dp[i - 1][rest - vw[i - 1][0]] + vw[i - 1][1]
                dp[i][rest] = max(r1, r2)
        
        return dp[n][V]

思路2：一维 DP（内存优化）

• 因为每次更新第 i 行数据时，只与 i-1 行有关，所以可以使用一维数组优化；

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算01背包问题的结果
# @param V int整型 背包的体积
# @param n int整型 物品的个数
# @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
# @return int整型
#
class Solution:
    def knapsack(self , V: int, n: int, vw: List[List[int]]) -> int:
        # write code here
        
        dp = [0] * (V + 1)
        dp[0] = 0  # 可以省略
        
        for i in range(1, n + 1):
            for rest in range(V, vw[i - 1][0] - 1, -1):
                # 不拿第 i 个物品
                r1 = dp[rest]
                # 拿第 i 个物品
                r2 = dp[rest - vw[i - 1][0]] + vw[i - 1][1]
                # 取较大的
                dp[rest] = max(r1, r2)
        
        return dp[V]

为什么一维 DP 中要逆序遍历体积？

二维状态的转移方程：dp[i][j]=max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);
一维状态的转移方程：dp[j]=max(dp[j], dp[j-v[i]] + w[i]);

可以看到二维中更新第 i 层数据用的都是 i - 1 层的数据，因为第 i - 1 层的数据已经固定，所以正序逆序遍历都无所谓；而如果在一维状态中正序遍历，那么 dp[j-v[i]] 会在 dp[j] 前被更新，导致 dp[j] 得到错误的答案；

关于01背包和完全背包的优化的体积顺序问题_听-起风了的博客-CSDN博客

思路3：另一种尝试

• 思路 1 是最直观的尝试方法；但存在一个问题，就是当 V 非常大时，可能会超时；
• 此时可以尝试另一个递推思路，定义 dp[i][w] 表示前 i 个物品达到重量为 w 时需要的最小空间；
• 最后的答案为满足 dp[n][w] <= V 时最大的 w；
• 事实上，对比后可以发现两者的转移方程非常相似：
  • 最大重量：dp[i] = max(dp[i], dp[i - v[i]] + w[i])
  • 最小空间：dp[i] = min(dp[i], dp[i - w[i]] + v[i])

Python：写法1）二维 DP

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算01背包问题的结果
# @param V int整型 背包的体积
# @param n int整型 物品的个数
# @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
# @return int整型
#
class Solution:
    def knapsack(self , V: int, n: int, vw: List[List[int]]) -> int:
        # write code here
        
        # 重量上限，即所有物品的重量和
        W = sum(it[1] for it in vw)
        
        # 初始化为无穷大
        #   也可以初始化为 -1，表示不能达到的重量，但是没有直接初始化为无穷大方便；
        dp = [[float('inf')] * (W + 1) for _ in range(n + 1)]
        dp[0][0] = 0  # 重量为 0 所需的最小空间也是 0
            
        for i in range(1, n + 1):
            for w in range(W + 1):
                r1 = dp[i - 1][w]
                r2 = float('inf')
                if w - vw[i - 1][1] >= 0:
                    r2 = dp[i - 1][w - vw[i - 1][1]] + vw[i - 1][0]
                dp[i][w] = min(r1, r2)
            
        for w in range(W, -1, -1):
            if dp[n][w] <= V:
                return w
            
        return 0

Python：写法2）一维 DP

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算01背包问题的结果
# @param V int整型 背包的体积
# @param n int整型 物品的个数
# @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
# @return int整型
#
class Solution:
    def knapsack(self , V: int, n: int, vw: List[List[int]]) -> int:
        # write code here
        
        # 最大重量
        W = sum(it[1] for it in vw)
        
        # 初始化为无穷大
        dp = [float('inf')] * (W + 1)
        dp[0] = 0  # 重量为 0 所需的最小空间也是 0
            
        for i in range(1, n + 1):
            for w in range(W, vw[i - 1][1] - 1, -1):
                dp[w] = min(dp[w], dp[w - vw[i - 1][1]] + vw[i - 1][0])
        
        # 逆序遍历 S，当找到需要的最小体积相遇等于 V 时，此时的 w 就是最大重量
        for w in range(W, -1, -1):
            if dp[w] <= V:
                return w
            
        return 0

代码验证

• 因为上面一些代码不能通过 OJ，所以离线写了一个对数器验证正确性（假设能通过 OJ 的 Solution1 是正确的）；

Python

from typing import *


class Solution1:
    def knapsack(self, V: int, n: int, vw: List[List[int]]) -> int:
        # write code here

        dp = [[0] * (V + 1) for _ in range(n + 1)]
        # 对应递归基：剩余容量为 V 时前 0 个物品的最大重量
        dp[0][V] = 0

        for i in range(1, n + 1):
            for rest in range(V + 1):  # 这里正序逆序遍历都可以
                # 与 dfs 的过程一一对应
                r1 = dp[i - 1][rest]
                r2 = 0
                if rest >= vw[i - 1][0]:
                    r2 = dp[i - 1][rest - vw[i - 1][0]] + vw[i - 1][1]
                dp[i][rest] = max(r1, r2)

        return dp[n][V]


class Solution2:
    def knapsack(self, V: int, n: int, vw: List[List[int]]) -> int:
        # write code here

        dp = [0] * (V + 1)
        dp[0] = 0  # 可以省略

        for i in range(1, n + 1):
            for rest in range(V, vw[i - 1][0] - 1, -1):
                # 不拿第 i 个物品
                r1 = dp[rest]
                # 拿第 i 个物品
                r2 = dp[rest - vw[i - 1][0]] + vw[i - 1][1]
                # 取较大的
                dp[rest] = max(r1, r2)

        return dp[V]


class Solution3:
    def knapsack(self, V: int, n: int, vw: List[List[int]]) -> int:
        # write code here

        # 最大重量
        W = sum(it[1] for it in vw)

        # 初始化为无穷大
        dp = [[float('inf')] * (W + 1) for _ in range(n + 1)]
        dp[0][0] = 0  # 重量为 0 所需的最小空间也是 0

        for i in range(1, n + 1):
            for w in range(W + 1):
                r1 = dp[i - 1][w]
                r2 = float('inf')
                if w - vw[i - 1][1] >= 0:
                    r2 = dp[i - 1][w - vw[i - 1][1]] + vw[i - 1][0]
                dp[i][w] = min(r1, r2)

        for w in range(W, -1, -1):
            if dp[n][w] <= V:
                return w

        return 0


class Solution4:
    def knapsack(self, V: int, n: int, vw: List[List[int]]) -> int:
        # write code here

        # 最大重量
        W = sum(it[1] for it in vw)

        # 初始化为无穷大
        dp = [float('inf')] * (W + 1)
        dp[0] = 0  # 重量为 0 所需的最小空间也是 0

        for i in range(1, n + 1):
            for w in range(W, vw[i - 1][1] - 1, -1):
                dp[w] = min(dp[w], dp[w - vw[i - 1][1]] + vw[i - 1][0])

        # 逆序遍历 S，当找到需要的最小体积相遇等于 V 时，此时的 w 就是最大重量
        for w in range(W, -1, -1):
            if dp[w] <= V:
                return w

        return 0


def random_input():
    import random
    MAX = 1000

    V = random.randint(1, MAX)
    n = random.randint(1, 100)  # 因为 方法 3, 4 比较慢，所以控制一下 n 的范围

    vw = []
    for _ in range(n):
        v, w = random.randint(1, MAX), random.randint(1, MAX)
        vw.append([v, w])

    return V, n, vw


def _test():
    """"""
    for _ in range(10):
        V, n, vw = random_input()
        r1 = Solution1().knapsack(V, n, vw)
        r2 = Solution2().knapsack(V, n, vw)
        r3 = Solution3().knapsack(V, n, vw)
        r4 = Solution4().knapsack(V, n, vw)

        assert r1 == r2 == r3 == r4


if __name__ == '__main__':
    """"""
    _test()

---