动态规划¶

约 5080 个字 59 行代码预计阅读时间 18 分钟

Reference¶

https://leetcode.cn/discuss/post/3581838/fen-xiang-gun-ti-dan-dong-tai-gui-hua-ru-007o/

爬楼梯¶

方案i和方案i-j有关

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

          ---
       ---|
    ---|

- n=2，求到达第n+1平台的方法数， 
- dp[0]：到达第1个平台的方法数，直接到，dp[0]=1
- dp[1]：到达第2个平台的方法数，直接到，dp[1]=1
- dp[n]: 到达第n+1个平台的方法数，
- dp[i]：到达第i+1个平台的方法数，dp[i]=dp[i-1]+dp[i-2]
- 注意，这里传n=1，至少有一个楼梯，不需要特判

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用. 一旦你支付此费用，即可选择向上爬一个或者两个台阶. 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯. 请你计算并返回达到楼梯顶部的最低花费. LC746使用最小花费爬楼梯 [x]
- cost = [10,15,20], dp[0,0,10,15]
- n=3，代表有三个平台，但是我们最终要知道第四个平台
- 所以dp长度为4
- dp[0]：到达第1个平台的费用，直接到，dp[0]=0
- dp[1]：到达第2个平台的费用，直接到，dp[1]=0
- dp[n]：
- 因为可以从第 i-1 或 i-2 个平台到达第 i 个平台，所以 dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]).
- 注意，这里题目给的cost数组长度最小为2，因此至少有2个楼梯（3个平台），可以不进行特判
给你一个由不同整数组成的数组 nums ，和一个目标整数 target . 请你从 nums 中找出并返回总和为 target 的元素组合的个数. 1 <= nums[i] <= 1000. nums 中的所有元素互不相同. LC377组合总和IV [x]
- 类比爬楼梯
- 到达target的方法数c

c = 0
for num in nums:
    if num<=target
        c = c + (target-num 对应的方法数)

- dp[0]: 到达0的方法数，啥都不用加也是0，dp[0]=1
- dp[target]: 到达target的方法数
- 特判，nums长度为1时，对于上面的循环内部if判断，如果num<target，可以得到c=0，如果num==target，会算出c=1，正确，因此不需要特判

打家劫舍¶

选择元素a，就不能选择元素a附近的

给定一个代表每个房屋存放金额的非负整数数组（如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警），计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额.
- 设 dp[i] 表示考虑到第 i 个房屋时能偷窃到的最高金额. 对于第 i 个房屋，有两种选择：
  - 偷第 i 个房屋，此时不能偷第 i-1 个房屋，所以 dp[i] = dp[i-2] + nums[i].
  - 不偷第 i 个房屋，那么 dp[i] = dp[i-1]. 最终的结果就是 dp[n-1]，其中 n 是房屋的数量. 初始条件为 dp[0] = nums[0]，dp[1] = max(nums[0], nums[1]).
这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的. 同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警. 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，今晚能够偷窃到的最高金额.
- 由于房屋是环形的，即第一个和最后一个房屋相邻，所以不能同时偷第一个和最后一个房屋. 因此，可以将问题分解为两个子问题：
  - 不考虑最后一个房屋，计算前 n-1 个房屋的最大偷窃金额.
  - 不考虑第一个房屋，计算后 n-1 个房屋的最大偷窃金额. 最终的结果是这两个子问题结果的最大值. 可以复用问题一的函数来计算这两个子问题.
给你一个数组power，其中每个元素表示一个咒语的伤害值，可能会有多个咒语有相同的伤害值. 已知魔法师使用伤害值为 power[i] 的咒语时，他们就不能使用伤害为 power[i] - 2 ，power[i] - 1 ，power[i] + 1 或者 power[i] + 2的咒语. 每个咒语最多只能被使用一次. 请你返回这个魔法师可以达到的伤害值之和的最大值.
- 首先对 power 数组进行排序，然后设 dp[i] 表示考虑到第 i 个咒语时能达到的最大伤害值之和. 对于第 i 个咒语，有两种选择：
  - 使用第 i 个咒语，此时不能使用 power[i] - 2，power[i] - 1，power[i] + 1 或者 power[i] + 2 的咒语，假设这些不能使用的咒语中最大的索引为 j（j < i），那么 dp[i] = dp[j] + power[i].
  - 不使用第 i 个咒语，那么 dp[i] = dp[i-1]. 最终的结果就是 dp[n-1]，其中 n 是咒语的数量. 初始条件为 dp[0] = power[0].

网格图DP¶

数组的索引通常对应于网格中的位置，数组的值代表了与该位置相关的某种最优解或计数

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小. 说明：每次只能向下或者向右移动一步. LC64最小路径和 [x]
- m=0, return 0
- m\neq 0, n=0 ,return 0
- dp[0][0]：就是grid[0][0]本身
- dp[0][j]：就是grid[0,:j+1]的和,1<=j<=n-1
- dp[i][0]：就是grid[:i+1,0]的和,1<=i<=m-1
- dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i][j], 1<=i,j
- dp[m-1][n-1]: 右下角
一个机器人位于一个 m x n 网格的左上角. 机器人每次只能向下或者向右移动一步. 机器人试图达到网格的右下角. 问总共有多少条不同的路径？LC62不同路径 [x]
- m=1 or n=1 return 1
- dp[0][0] = 1
- dp[0][j] = 1
- dp[i][0] = 1
- dp[i][j] = dp[i-1][j] + dp[i][j-1]
给定一个 m x n 的整数数组 grid. 一个机器人初始位于左上角（即 grid[0][0]）. 机器人尝试移动到右下角（即 grid[m - 1][n - 1]）. 机器人每次只能向下或者向右移动一步. 网格中的障碍物和空位置分别用 1 和 0 来表示. 机器人的移动路径中不能包含任何有障碍物的方格. 返回机器人能够到达右下角的不同路径数量. LC62不同路径|| [x]
- dp[0][0] = 1 if grid[0][0]==0 else dp[0][0] = 0
- dp[0][j]: if grid[0][j]==0: dp[0][j] = dp[0][j-1] else: dp[0][j] = 0
- dp[i][0]: if grid[i][0]==0: dp[i][0] = dp[i-1][0] else: dp[i][0] = 0
- dp[i][j]: if grid[i][j]==0: dp[i][j] = dp[i-1][j] + dp[i][j-1] else: dp[i][j] = 0
- dp[m-1][n-1]：右下角
给你一个 n x n 的方形整数数组 matrix ，请你找出并返回通过 matrix 的下降路径的最小和 . 下降路径可以从第一行中的任何元素开始，并从每一行中选择一个元素. 在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）. 具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) .
给定一个三角形 triangle ，找出自顶向下的最小路径和. 每一步只能移动到下一行中相邻的结点上. 相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点. 也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 .

背包¶

01背包¶

在 0 - 1 背包问题中，有一个容量为 C 的背包和 n 个物品，每个物品有重量 w[i] 和价值 v[i]，目标是在不超过背包容量的前提下，选择一些物品使得总价值最大. - 状态定义定义状态dp[i][j]表示前i个物品放入容量为j的背包中所能获得的最大价值. - 状态转移方程当j < w[i]时，即背包容量不足以放入第i个物品，此时dp[i][j] = dp[i - 1][j]，即不放入第i个物品，价值与前i - 1个物品放入背包时相同. 当j >= w[i]时，有两种选择：放入第i个物品或不放入. 放入时，价值为dp[i - 1][j - w[i]] + v[i]；不放入时，价值为dp[i - 1][j]. 取两者中的较大值，即dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j]). - 初始化 dp[0][j] = 0，表示没有物品放入背包时，价值为 0. dp[i][0] = 0，表示背包容量为 0 时，价值为 0. - 计算顺序按照物品的数量i从 1 到n，背包容量j从 1 到C的顺序进行计算. - 最终答案 dp[n][C]即为将n个物品放入容量为C的背包中所能获得的最大价值.

def knapsack_01_2d(n, C, w, v):
    # 创建一个二维数组 dp，dp[i][j] 表示前 i 个物品放入容量为 j 的背包中能获得的最大价值
    dp = [[0 for _ in range(C + 1)] for _ in range(n + 1)]

    # 遍历每个物品
    for i in range(1, n + 1):
        # 遍历每个可能的背包容量
        for j in range(1, C + 1):
            # 如果当前物品的重量大于当前背包容量，不能放入该物品
            if w[i - 1] > j:
                dp[i][j] = dp[i - 1][j]
            else:
                # 考虑放入或不放入当前物品，取价值较大的情况
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1])

    return dp[n][C]

一维优化代码：

def knapsack_01_space_optimized(n, C, w, v):
    # 创建一维数组并初始化
    dp = [0] * (C + 1)

    # 动态规划计算
    for i in range(n):
        for j in range(C, w[i] - 1, -1):
            dp[j] = max(dp[j - w[i]] + v[i], dp[j])

    return dp[C]

给你一个只包含正整数的非空数组 nums . 请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等.
- 背包容量：先计算数组 nums 中所有元素的总和 sum_val，若 sum_val 为奇数，显然无法分割成两个和相等的子集；若为偶数，目标和 target = sum_val // 2，这个 target 就相当于 0 - 1 背包问题中的背包容量.
- 物品重量：数组 nums 中的每个元素 nums[i] 相当于一个物品的重量，且物品的价值在这里可以忽略，因为我们只关心能否凑出目标和.
- 物品选择：对于每个元素 nums[i]，有选和不选两种决策，这与 0 - 1 背包问题中每个物品只能选择放入或不放入背包的情况一致.
给你一个下标从 0 开始的整数数组 nums 和一个整数 target . 返回和为 target 的 nums 子序列中，子序列长度的最大值 . 如果不存在和为 target 的子序列，返回 -1 . 子序列指的是从原数组中删除一些或者不删除任何元素后，剩余元素保持原来的顺序构成的数组.
- 背包容量：目标值 target 相当于 0 - 1 背包问题中的背包容量.
- 物品重量：数组 nums 中的每个元素 nums[i] 相当于物品的重量.
- 状态定义：定义 dp[i][j] 表示在前 i 个元素中，和为 j 的子序列的最大长度，这类似于 0 - 1 背包问题中用二维数组记录状态.
- 状态转移：状态转移方程考虑选或不选当前元素，与 0 - 1 背包问题的决策过程一致.
给你两个正整数 n 和 x . 请你返回将 n 表示成一些互不相同正整数的 x 次幂之和的方案数. 换句话说，你需要返回互不相同整数 [n1, n2, ..., nk] 的集合数目，满足 n = n1^x + n2^x + ... + nk^x .
- 背包容量：目标值 n 相当于 0 - 1 背包问题中的背包容量.
- 物品重量：正整数的 x 次幂 i ** x 相当于物品的重量.
- 物品选择：对于每个正整数 i，可以选择将其 x 次幂加入到当前和中，或者不加入，这和 0 - 1 背包问题中物品的选择方式类似.

完全背包¶

完全背包问题不同之处在于每种物品可以无限次地放入背包. - 定义状态：设dp[i][j]表示前i种物品放入容量为j的背包中所能获得的最大价值. - 状态转移方程：对于第i种物品，有两种决策，要么不选，要么选. 由于每种物品可以选无限次，所以状态转移方程为dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i])，其中w[i]是第i种物品的重量，v[i]是第i种物品的价值. 这表示不选第i种物品时的最大价值，和选了第i种物品（可多次选）放入背包剩余容量j - w[i]时的最大价值中的较大值. - 初始化：dp[0][j] = 0，表示没有物品时，无论背包容量是多少，价值都为 0；dp[i][0] = 0，表示背包容量为 0 时，无论有多少物品，价值也为 0. - 计算顺序：一般先遍历物品，再遍历背包容量. 对于每种物品，从背包容量为 0 开始逐步计算到背包的总容量. 这样可以保证在计算dp[i][j]时，dp[i][j - w[i]]已经是考虑了前i种物品（包括当前物品i可多次选）放入容量为j - w[i]的背包中的最大价值. - 最终答案：dp[n][C]即为将n种物品放入容量为C的背包中所能获得的最大价值.

def complete_knapsack_2d(n, C, w, v):
    # 创建二维数组 dp，dp[i][j] 表示前 i 种物品放入容量为 j 的背包能获得的最大价值
    dp = [[0 for _ in range(C + 1)] for _ in range(n + 1)]

    # 遍历每种物品
    for i in range(1, n + 1):
        # 遍历每个可能的背包容量
        for j in range(1, C + 1):
            # 不选第 i 种物品的情况
            dp[i][j] = dp[i - 1][j]
            if j >= w[i - 1]:
                # 选第 i 种物品，由于每种物品可以选多次，状态转移到 dp[i][j - w[i - 1]]
                dp[i][j] = max(dp[i][j], dp[i][j - w[i - 1]] + v[i - 1])

    return dp[n][C]

注意：在 01 背包问题中，我们是从背包容量的最大值m开始递减遍历到w[i]，以保证每个物品只能使用一次. 而在完全背包问题中，我们需要从w[i]开始递增遍历到m，这样才能保证每种物品可以被多次放入背包.

一维优化代码

def knapsack_complete(n, C, w, v):
    # 创建一维数组并初始化
    dp = [0] * (C + 1)

    # 遍历每种物品
    for i in range(n):
        # 遍历背包容量，注意这里是从小到大遍历
        for j in range(w[i], C + 1):
            dp[j] = max(dp[j], dp[j - w[i]] + v[i])

    return dp[C]

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额. 计算并返回可以凑成总金额所需的最少的硬币个数 . 如果没有任何一种硬币组合能组成总金额，返回 -1 . 你可以认为每种硬币的数量是无限的.
- 可以将硬币的面额看作完全背包问题中的物品重量，将总金额看作背包的容量，而每个 “物品”（硬币）可以无限次使用，目标是求凑出 “背包容量”（总金额）所需 “物品”（硬币）的最少数量.
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额. 请你计算并返回可以凑成总金额的硬币组合数. 如果任何硬币组合都无法凑出总金额，返回 0 . 假设每一种面额的硬币有无限个.
- 可以把硬币面额当作完全背包问题中的物品重量，总金额当作背包容量，每个物品（硬币）可无限次使用，目标是求凑出 “背包容量”（总金额）的 “物品”（硬币）组合数.
给你一个整数 n ，返回和为 n 的完全平方数的最少数量 . 完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积. 例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是.
- 把每个完全平方数看作完全背包问题中的物品，其值为物品的重量，n为背包的容量，每个 “物品”（完全平方数）可以无限次使用，目标是求凑出 “背包容量”（整数n）所需 “物品”（完全平方数）的最少数量.

最长公共子序列（LCS）¶

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度. 如果不存在公共子序列，返回 0 . 一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串. 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列. 两个字符串的公共子序列是这两个字符串所共同拥有的子序列.
- 定义dp[i][j]为text1的前i个字符和text2的前j个字符的最长公共子序列的长度.
- 状态转移方程为：
  - 当text1[i-1] == text2[j-1]时，dp[i][j] = dp[i-1][j-1] + 1
  - 当text1[i-1] != text2[j-1]时，dp[i][j] = max(dp[i-1][j], dp[i][j-1])
给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数 . 你可以对一个单词进行如下三种操作：插入一个字符、删除一个字符、替换一个字符.
- 定义dp[i][j]为将word1的前i个字符转换成word2的前j个字符所需的最少操作数.
- 状态转移方程为：
  - 当word1[i-1] == word2[j-1]时，dp[i][j] = dp[i-1][j-1]
  - 当word1[i-1] != word2[j-1]时，dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1)
给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数. 每步可以删除任意一个字符串中的一个字符.
- 定义dp[i][j]为使得word1的前i个字符和word2的前j个字符相同所需的最小步数.
- 状态转移方程为：
  - 当word1[i-1] == word2[j-1]时，dp[i][j] = dp[i-1][j-1]
  - 当word1[i-1] != word2[j-1]时，dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1)

最长递增子序列（LIS）¶

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度. 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序. 例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列.
- 定义dp[i]为以nums[i]结尾的最长严格递增子序列的长度.
- 状态转移方程为：对于所有的j < i，如果nums[j] < nums[i]，则dp[i] = max(dp[i], dp[j] + 1).
- 最终结果为dp数组中的最大值.
给你一个整数数组 nums . nums 的每个元素是 1，2 或 3. 在每次操作中，你可以删除 nums 中的一个元素. 返回使 nums 成为非递减顺序所需操作数的最小值.
- 可以先找出数组中的最长非递减子序列的长度，然后用数组的总长度减去最长非递减子序列的长度，就可以得到使数组成为非递减顺序所需的最小删除操作数.

划分型 DP¶

给你一个字符串 s 和一个字符串列表 wordDict 作为字典. 如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true. 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用.
- 定义 dp[i] 表示字符串 s 的前 i 个字符是否可以由字典中的单词拼接而成. 状态转移方程为：对于所有 0 <= j < i，如果 dp[j] 为 True 且 s[j:i] 在字典中，则 dp[i] 为 True.
给你一个下标从 0 开始的字符串 s 和一个单词字典 dictionary . 你需要将 s 分割成若干个互不重叠的子字符串，每个子字符串都在 dictionary 中出现过. s 中可能会有一些额外的字符不在任何子字符串中. 请你采取最优策略分割 s ，使剩下的字符最少 .
- 定义 dp[i] 表示字符串 s 的前 i 个字符分割后剩余的最少字符数. 状态转移方程为：对于所有 0 <= j < i，如果 s[j:i] 在字典中，则 dp[i] = min(dp[i], dp[j])；否则 dp[i] = dp[i - 1] + 1.
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串. 返回符合要求的最少分割次数 . 子串是字符串中连续的非空字符序列.
- 先预处理出所有子串是否为回文串，然后定义 dp[i] 表示字符串 s 的前 i 个字符分割成回文子串的最少分割次数. 状态转移方程为：对于所有 0 <= j < i，如果 s[j:i] 是回文串，则 dp[i] = min(dp[i], dp[j] + 1).

状态机 DP¶

一般定义 f[i][j] 表示前缀 a[:i] 在状态 j 下的最优值. j 一般很小.

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格. 你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票. 设计一个算法来计算你所能获取的最大利润. 返回你可以从这笔交易中获取的最大利润. 如果你不能获取任何利润，返回 0 .
- dp[i][0] 表示第 i 天不持有股票的最大利润，dp[i][1] 表示第 i 天持有股票的最大利润.
- 状态转移方程如下：
  - dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
  - dp[i][1] = max(dp[i - 1][1], -prices[i])
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格. 在每一天，你可以决定是否购买和/或出售股票. 你在任何时候最多只能持有一股股票. 你也可以先购买，然后在同一天出售. 返回你能获得的最大利润 .
- dp[i][0] 表示第 i 天不持有股票的最大利润，dp[i][1] 表示第 i 天持有股票的最大利润.
- 状态转移方程如下：
  - dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
  - dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格. 设计一个算法来计算你所能获取的最大利润. 你最多可以完成两笔交易. 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）.
- dp[i][j] 中 j 有 5 种状态，分别为： j = 0：没有任何操作 j = 1：第一次买入 j = 2：第一次卖出 j = 3：第二次买入 j = 4：第二次卖出
- 状态转移方程如下：
  - dp[i][0] = dp[i - 1][0]
  - dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
  - dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i])
  - dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i])
  - dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i])
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格. 设计一个算法来计算你所能获取的最大利润. 你最多可以完成 k 笔交易. 也就是说，你最多可以买 k 次，卖 k 次. 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）.
- dp[i][j] 中 j 有 2 * k + 1 种状态，j 为偶数表示不持有股票，j 为奇数表示持有股票.
- 状态转移方程如下：
  - 当 j = 0 时，dp[i][0] = dp[i - 1][0]
  - 当 j 为奇数时，dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i])
  - 当 j 为偶数且 j > 0 时，dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i])
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 . 设计一个算法计算出最大利润. 在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）: 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天). 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）.
- dp[i][j] 中 j 有 3 种状态：
  - j = 0：持有股票
  - j = 1：不持有股票且不在冷冻期
  - j = 2：不持有股票且在冷冻期
- 状态转移方程如下：
  - dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])
  - dp[i][1] = max(dp[i - 1][1], dp[i - 1][2])
  - dp[i][2] = dp[i - 1][0] + prices[i]
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格；整数 fee 代表了交易股票的手续费用. 你可以无限次地完成交易，但是你每笔交易都需要付手续费. 如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了. 返回获得利润的最大值. 注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费.
- dp[i][0] 表示第 i 天不持有股票的最大利润，dp[i][1] 表示第 i 天持有股票的最大利润.
- 状态转移方程如下：
  - dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee)
  - dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])

三维DP¶

给你一个大小为 m x n 的二维整数数组 grid 和一个整数 k . 你的任务是统计满足以下条件且从左上格子 (0, 0) 出发到达右下格子 (m - 1, n - 1) 的路径数目：每一步你可以向右或者向下走，也就是如果格子存在的话，可以从格子 (i, j) 走到格子 (i, j + 1) 或者格子 (i + 1, j) . 路径上经过的所有数字 XOR 异或值必须等于 k . 请你返回满足上述条件的路径总数.
对于给定的由 \(n\) 个正整数构成的数组 \(\{a_1, a_2, \ldots, a_n\}\)，从中选择至多 \(k\) 个数，使得这些数的乘积恰好为 \(p\) 的倍数。一共有多少种满足条件的选数方案？

动态规划¶

Reference¶

爬楼梯¶

打家劫舍¶

网格图DP¶

背包¶

01背包¶

完全背包¶

最长公共子序列（LCS）¶

最长递增子序列（LIS）¶

划分型 DP¶

状态机 DP¶

三维DP¶

树形DP¶

前后缀分解结合DP¶

区间DP¶

状压DP¶

数位DP¶