动态规划

斐波那契型

一般是直观的状态转移 选或不选的问题

dp[i] 表示前i个最多能有多少钱 每个选还是不选？因为选了这个 就不能选下一个 由此得出状态转移方程 dp[i] = max(dp[i - 2] + cost[i], dp[i - 1]) 选了这个 就需要加上这个的值（并且不能选i - 1） 不选这个 就直接从i - 1转移

初始化 视情况而定 一般初始化 dp[0] 、dp[1] 等 前几个元素

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

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 3:
            return max(nums)
        dp = [0] * (n + 1)
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, n):
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
        return dp[n - 1]

740. 删除并获得点数 - 力扣（LeetCode）](https://leetcode.cn/problems/delete-and-earn/?envType=study-plan-v2&envId=dynamic-programming)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        n = max(nums)
        cost = [0] * (n + 1)
        for i, x in enumerate(nums):
            cost[x] += x
        dp = [0] * (n + 1)
        dp[0] = cost[0]
        dp[1] = cost[1]
     
        for i in range(2, n + 1):
            dp[i] = max(dp[i - 2] + cost[i], dp[i - 1])
        return dp[n]

矩阵型

一般是类似于走迷宫 用二维的 dp[i] [j]

i，j表示坐标 状态从上一坐标 转移而来 一般是相邻的位置 比如i - 1 j - 1 等

注意 这类问题 一般需要判断该位置是否已经走过？ 比如求最大值可以设初值为0 判断为0即未访问 求最小值设为inf等

得到状态转移方程为 dp[i] [j] = max(dp[i - 1] [j], dp[i] [j - 1]) + cost[]

初始化一般是用于转移的前几个数

由于数组的原因 下标经常从1开始 到n+1结束 相应的cost数组的下标也需要改变

62. 不同路径 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if n == 1 or m == 1:
            return 1
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        dp[1][1] = 0
        dp[1][2] = dp[2][1] = 1
        for i in range(m):
            for j in range(n):
                if dp[i][j] == 0:
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[m][n]

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

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        dp = [[10 ** 9] * (n + 1) for i in range(m + 1)]
        dp[1][1] = grid[0][0]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if dp[i][j] == 10 ** 9:
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1]
        return dp[m][n]

221. 最大正方形 - 力扣（LeetCode）

这题同样是矩阵型

dp[i] [j] 表示以i j 为右下角的最大正方形的 边长 每次看他的上、左和上左 三个格子的最大边长 + 1

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m = len(matrix)
        n = len(matrix[0])
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(m):
            for j in range(n):
                if matrix[i - 1][j - 1] == '1':
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
                ret = max(ret, dp[i][j])
        return ret ** 2

2304. 网格中的最小路径代价 - 力扣（LeetCode）

想到 从第一行开始取数 然后向下转移

比如g[0] [0] 就可以到 g[1] [0]….g[1] [m - 1]这样

于是用dfs(i, j) 来表示状态 在第i行第j列的最小值

然后就要考虑怎么递增 从i j 递增到下一行的第k个 那么下一行第k个的值 就是dfs(i + 1, k) + moveCost[grid[i] [j]] [k]

然后考虑退出条件 不断向下 那肯定就是到第n - 1行结束

结束的时候要返回什么？ 这和存的东西 有关 dfs（i, j）表示i j 的最小值 然后往下转移 最后一行不再往下转移 最小值就是它本身

然后通过这个转移的过程 可以发现 i j处的最小值 其实是i j 加上 从i j往下 的所有的（也就是 我们最后会把所有的都加到第0行 返回第0行的最小值）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        def dfs(i, j):
            if i == n - 1:
                return grid[i][j]
           	ret = inf
            # 注意 这里算的是 i j 的最小值 那就是i j 往下转移到下一行每一个 求最小
            for k, c in enumerate(moveCost):
                res = min(res, dfs(i + 1, k) + c)
            return res + grid[i][j] # 记得加上grid
        # 由dfs函数 就可以计算出 i j的最小值 -》算出0 j 的最小值 所以 还需要遍历0~m-1找第0行的最小值
        return min(dfs(0, j) for j in range(m))

然后翻译成递推

  • dfs改dp
  • 递归改循环
  • 递归边界改为dp初始值
  • 递归入口即为答案

dfs(i, j) -> dp[i] [j] 几个参数 就是几维

dp[-1] = grid[-1] 递归的边界 最后一行 就是初始值 因为我们算i j 的时候 其实是必须先算出来 i + 1 k 的值 然后再往上转移的

所以i要从下往上遍历 最后dp[0] 的最小值就是答案

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        dp = [[inf] * m for _ in range(n)]
        dp[-1] = grid[-1]
        for i in range(n - 2, -1, -1):
            for j in range(m):
                for k, c in enumerate(moveCost):
                    dp[i][j] = min(dp[i + 1][k] + c, dp[i][j])
             	dp[i][j] += grid[i][j]
        return min(dp[0])

1212. 地宫取宝 - AcWing题库

这个题目与上一个题有点像 都是矩阵型 状态转移方程也是由左(j - 1)上(i - 1)转移到[i, j]

四维DP 状态表示 dp[i] [j] [cnt] [d] 表示i到j中 拿到cnt个物品且最大价值为d的情况

状态计算 有选或不选两种 （只有当拿的东西不多于k并且价值大于当前最大价值才可以拿）

不选就直接转移 dp[i] [j] [c] [d] = (dp[i] [j] [c] [d] + dp[i - 1] [j] [c] [d]) % mod;

选的话 需要从c - 1转移过来 并且要加上所有价值小于d的情况

最后需要加上所有的最大价值的情况 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
using namespace std;
int row, col, k;
const int N = 55, mod = 1e9+7, M = 15;
int nums[N][N], dp[N][N][M][M];
int main()
{
    cin>>row>>col>>k;
    for (int i = 1; i <= row; i++)
    {
        for (int j = 1; j <= col; j++)
        {
            cin>>nums[i][j];
            nums[i][j]++;
        }
    }
    dp[1][1][0][0] = 1;
    dp[1][1][1][nums[1][1]] = 1;
    for (int i = 1; i <= row; i++)
    {
        for (int j = 1; j <= col; j++)
        {
            for (int c = 0; c <= k; c++)
            {
                for (int d = 0; d < M; d++)
                {
                    // 不选
                    dp[i][j][c][d] = (dp[i][j][c][d] + dp[i - 1][j][c][d]) % mod;
                    dp[i][j][c][d] = (dp[i][j][c][d] + dp[i][j - 1][c][d]) % mod;
                    // 选
                    if (c > 0 && d == nums[i][j])
                    {
                        for (int s = 0; s < d; s++)
                        {
                            dp[i][j][c][d] = (dp[i][j][c][d] + dp[i - 1][j][c - 1][s]) % mod;
                            dp[i][j][c][d] = (dp[i][j][c][d] + dp[i][j - 1][c - 1][s]) % mod;
                        }
                    }
                }
            }
        }
    }
    int res = 0;
    for (int i = 0 ;i < M; i++)
    {
        res = (res + dp[row][col][k][i])%mod;
    }
    cout<<res;
}

单字符串型

在单个字符串上进行操作 一般状态表示也是两个变量 i， j 然后取出一个区间 j 一般表示端点 s[i:j]或s[j: i]

初始化 一般需要初始化大量的字符串 比如 回文串 需要初始化每个s[i:i] 为1

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

dp[i] [j] 表示i到j是否为回文串 状态转移为 看12…..21 比如 1 == 1 那就看前面 一段2…..2是不是回文

如果1 != 1 那就直接false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s
       	begin = 0
     	max_len = 1
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
        # 枚举长度L
        for L in range(2, n + 1):
            for i in range(n):
                j = i + L - 1
                if j >= n:
                    break
                if s[i] != s[j]:
                    dp[i][j] = False
                else:# s[i] = s[j]  那就看前一段是不是回文 
                    if L < 3:
                        dp[i][j] = True
                    else:
                    	dp[i][j] = dp[i + 1][j - 1]
                if dp[i][j] and j - i + 1 > max_len:
                    max_len = j - i + 1
                    begin = i
        return s[begin:begin + max_len]

139. 单词拆分 - 力扣（LeetCode）

跟前一题很像 用dp[i]表示 前i个能不能被word拼接 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        dp = [False] * (n + 1)
        for i in range(1, n + 1):
            for j in range(i):
                if dp[i] == True:
                    continue
                if dp[j] == False:
                    continue
                # 当前i个是False 并且前j个事True的时候  就要从j转移到i 
                if s[j:i] in wordDict:
                    s[i] = True
                    break
         return dp[-1]

516. 最长回文子序列 - 力扣（LeetCode）

子序列问题 不连续 一般就要用i 和 j

dp[i] [j] 表示i 到j 最长是多少

当s[i] == s[j]的时候 dp[i] [j] 就可以从dp[i + 1] [j - 1]更新来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        for i in range(n):
            dp[i][i] = 1
        ret = 0
        for i in range(n - 1, -1, -1):
            for j in range(i + 1):
                if s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1] + 2
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
            ret = max(ret, dp[i][j])
        return ret

双字符串型

双字符串的题一般要用dp[i] [j] 一个用来表示第一个字符串的 第i个 一个用来表示第2个字符串的前j个

72. 编辑距离 - 力扣（LeetCode）

dp[i] [j] 表示第一个到i 第二个到j 相同的最小编辑次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        """def dfs(i, j):
            if i < 0:
                return j + 1
           	if j < 0:
                return i + 1
           	if word1[i] == word2[j]:
                return dfs(i - 1, j - 1)
            return min(dfs(i - 1, j), dfs(i, j - 1), dfs(i - 1, j - 1)) + 1"""
        # dfs 转 dp
        n, m = len(word1), len(word2)
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        dp[0] = list(range(m + 1))
        for i in range(n):
            dp[i + 1][0] = i + 1
            for j in range(m):
                if word1[i] == word2[j]:
                    dp[i + 1][j + 1] = dp[i][j]
                else:
                    dp[i + 1][j + 1] = min(dp[i][j], dp[i][j + 1], dp[i + 1][j]) + 1
        return dp[n][m]

115. 不同的子序列 - 力扣（LeetCode）

这题与上一题不同 在于 上一题是修改s使其与 t相等 所以 不相等的时候只需要修改 就可以相等 然后位移指针

但是这个题 是求t在x中出现的次数 也就是说t 必须全部匹配 所以t的指针j 只有在匹配的时候才能位移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        """def dfs(i, j):
            if i < 0:
                return 0
            if j < 0:
                return 1 # 表示已经匹配
           	if s[i] == t[j]:
                return dfs(i - 1, j - 1) + dfs(i - 1, j)  # 选或不选两种情况
            return dfs(i - 1, j)
       	"""
        n, m = len(s), len(t)
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        
        for i in range(n):
            for j in range(m):
                if j == 0:
                    dp[i][0] = 1
                elif s[i] == t[j]:
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
                else:
                    dp[i][j] = dp[i - 1][j]
        return dp[n][m]

712. 两个字符串的最小ASCII删除和 - 力扣（LeetCode）

由于直接求最小不好求 可以选择 先求出两个字符串的ascll总和 然后求最长子序列 最后再减去最长子序列的ascll * 2 就是删除的最小和

dp[i] [j] 表示最长子序列的ascll和 （即 到s1[i] s2[j]的ascll和）

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution: 
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        n, m = len(s1), len(s2)
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        s = sum([ord(s1[i]) for i in range(n)])
        s += sum([ord(s2[i]) for i in range(m)])
        for i in range(n):
            for j in range(m):
                if s1[i] == s2[j]:
                    dp[i + 1][j + 1] = dp[i][j] + ord(s1[i])
                else:
                    dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
        return s - dp[n][m] * 2

673. 最长递增子序列的个数 - 力扣（LeetCode）

先是找最长的递增子序列 用maxn记录最长的长度 dp[i] 记录到i的最长子序列长度 （最长递增子序列）

由于本题求得是个数 需要增加cnt[i] 表示 到i 的最长递增子序列的个数

对于每个i 遍历0 ~ i的每个j 如果nums[i] > nums[j] 说明i 可以接在j后面形成递增子序列

如果dp[i] < dp[j] + 1那么说明到i的最长递增子序列的长度需要更新 那么到i 的最长子序列的数量 可以直接更新(到j的数量 直接转移到 到i的数量 )

如果dp[i] == dp[j] + 1 那么说明到i这个地方 他的最长递增子序列（并非整个数组最长而是0~i最长）的数量+= 到j的数量

最后把到每个i 的等于maxn的数量加起来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * (n + 1)
        cnt = [0] * (n + 1)
        maxn = -1
        for i in range(n):
            dp[i] = 1
            cnt[i] = 1
            for j in range(i):
                if nums[i] > nums[j]:
                    if dp[i] < dp[j] + 1:
                        dp[i] = dp[j] + 1
                        cnt[i] = cnt[j]
                    elif dp[i] == dp[j] + 1:
                        cnt[i] += cnt[j]
            maxn = max(maxn, dp[i])
        ret = 0
        for i in range(n):
            if dp[i] == maxn:
                ret += cnt[i]
        return ret

646. 最长数对链 - 力扣（LeetCode）

模板题 最长上升子序列

状态表示dp[i] 表示到i 到j 的最长链

状态转移 i + 1的l如果大于i的r

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        n = len(pairs)
        pairs.sort(key=lambda x: (x[0], x[1]))
        dp = [0] * (n + 1)
        for i in range(n):
            dp[i] = 1
            for j in range(n):
                if pairs[j][1] < pairs[i][0]:
                    dp[i] = max(dp[j] + 1, dp[i])
                
        return max(dp)

公共子序列型

一般需要二维 i用来表示到text1 j表示到text2 的时候最长公共子序列为多长

更新状态一般是当text1[i - 1] == text2[i - 1]的时候就是dp[i] [j] = dp[i - 1] [j - 1] + 1 意思是到i j 公共子序列长度增加

否则就是选出dp[i - 1] [j] 和dp[i] [j - 1] 中较大的

1143. 最长公共子序列 - 力扣（LeetCode）

dp[i] [j] 

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[m][n]

0数组切分 - 蓝桥云课 (lanqiao.cn)

类似最长子串的问题 判断条件变为 连续数字

判断连续的数字 就用i - j == max - min 从i到j中的最大值与最小值的差等于i - j的话 那么这个范围内的数字就是连续的

dp[i] 表示前i个数共有多少种表示方法

二重循环从i到0 倒着找 如果找到了一个范围j~i使得里面的数字连续的话 (原来前i个数 共有dp[i] 种表示方法 前j - 1个数共有dp[j - 1]种) 那么现在dp[i] = dp[i] + dp[j - 1] 因为前j - 1的方案数 现在j ~i也可以了 就可以接上 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
using namespace std;
int a[100010], dp[100010];
int mod = 1e9 + 7;
int main()
{
    int n;
    cin>>n;

    for (int i = 1; i <= n; i++)
    {
        cin>>a[i];
    }
    dp[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        int ma = a[i], mi = a[i];
        for (int j = i; j > 0; j--)
        {
            if (i - j == ma - mi)
            {
                dp[i] = (dp[i] + dp[j - 1]) % mod;
            }
        }
    }
    cout<<dp[n];
    return 
}

1035. 不相交的线 - 力扣（LeetCode）

最长公共子序列 同时要满足线不能相交（也就是要有序 ）其实跟最长公共子序列一样

1312. 让字符串成为回文串的最少插入次数 - 力扣（LeetCode）

也是最长公共子序列 只不过不是两个字符串 而是一个字符串 从前往后 一个字符串从后往前 来比较

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def minInsertions(self, s: str) -> int:
        n = len(s)
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        for i in range(n):
            dp[i][i] = 1
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1] + 2
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j  - 1])
        return n - dp[0][n - 1]

树上DP

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

求二叉搜索树的种数 就是G[0] = 1 G[1] = 1 G[2] = 2

image-20231125183323873

卡特兰数

1
2
3
4
5
6
7
8
9
class Solution:
    def numTrees(self, n: int) -> int:
        g = [0] * (n + 1)
        g[0] = 1
        g[1] = 1
        for i in range(2, n + 1):
           	for j in range(1, i + 1):
                g[i] += g[j - 1] * g[i - j]
        return g[n]

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

搜索 首先想要递归什么？递归start和end 就是每棵树包含start到end的元素

递归出口条件 就是当start < end 的时候 说明没有元素 return None

然后思考如何去递归 既然是递归start和end中间的元素 那么就可以想到 左子树是start到i 右子树是i+1到end 然后再去把这两个树加上根节点拼起来 存入答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        def generate(start, end):
            if start > end:
                return [None, ]
            alltrees = []
            for i in range(start, end + 1):
                leftTree = generate(start, i)
                rightTree = generate(i + 1, end)
            for l in leftTree:
                for r in rightTree:
                    curTree = TreeNode(i)
                    curTree.left = l
                    curTree.right = r
                   	allTree.append(curTree)
            return allTrees
        return generate(1, n) if n else []

337. 打家劫舍 III - 力扣（LeetCode）

首先思考怎么表示状态 偷或不偷 返回值表示 左边偷的钱 和右边偷的钱 如果左边或右边偷了 那么根就不能偷 否则偷根

递归出口 当root is None的时候 就返回0，0 表示

然后是每个 当dfs(root.left) 表示偷左不偷右 right同理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        def dfs(root):
            if root is None:
                return 0, 0
            l_rob, r_not_rob = dfs(root.left)
            l_not_rob, r_rob = dfs(root.right)
            rob = root.val + l_not_rob + r_not_rob
            # not_rob = l_rob + r_rob不偷根 也不一定必须偷左右  而是可以偷左右
            not_rob = max(l_rob, l_not_rob) + max(r_rob, r_not_rob)
            return rob, not_rob
       	return max(dfs(root))

124. 二叉树中的最大路径和 - 力扣（LeetCode）

首先思考递归表示 root

然后是递归出口 当root is None的时候 返回0

然后是算出左边的结点 右边的结点 再加上中间的 求最大值

返回最大值 注意最后的返回值要和0比较 因为有负数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        ans = -inf
        def dfs(root):
            if root is None:
                return 0
            
            l_val = dfs(root.left)
            r_val = dfs(root.right)
            nonlocal ans 
            ans = max(l_val + r_val + root.val, ans)
            return max(max(l_val, r_val) + root.val, 0)
        dfs(root)
        return ans

背包

1155. 掷骰子等于目标和的方法数 - 力扣（LeetCode）

分组背包 总和为n 每个骰子只能有一个点数 选哪个的问题

并且不是分组背包求最大值的问题 而是分组背包求固定和的问题 用的转移方程是 j - ds

第三重循环枚举点数 即 从dp[i - 1] 转移到dp[i] 的情况 有dp[i - 1] [j - 1] + 1；dp[i - 1] [j - 2] + 2 ……dp[i - 1] [j - k] + k 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        mod = 10 ** 9 + 7
		# 注意数组的范围 由于可能遍历计算的最大值是超过target的 所以这里不能开target
        dp = [[0] * (max(target + 1, n * k + 1)) for _ in range(n + 1)]
        # 注意初始化 j = 0 的时候不可能 即种数为0 大于k的时候也为0 因为一个骰子最多是k（大于target不用算了 所以为0）
        for i in range(1, min(target, k) + 1):
            dp[1][i] = 1
        # 算到n * k因为n * k 可能小于target 这时候为0
        maxn = n * k
        # 前两个循环 是枚举dp[i][j] 前i个骰子 和为j有几种情况
        for i in range(2, n + 1):
            for j in range(i, maxn + 1):
                # 第三个循环 状态转移 枚举第n - 1个骰子的点数 转移到i
                ds = 1
                while  j - ds >= 0 and ds <= k:
                    dp[i][j] += dp[i - 1][j - ds]
                    dp[i][j] %= mod
                    ds += 1
        
        return dp[n][target]

组合型背包

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

这个题目与上题有区别 一个是求排列数 一个是求组合数

也就是说 上一题会把1 2 和2 1当成两种情况 但是这一题 视为同一种情况 如果按上面的写法 最后结果会偏大

本质原因是子问题的改变 我们需要加上对硬币的限制 1 2 和 2 1 是同种情况 因此可以枚举硬币而不是枚举总和 从小到大枚举硬币 就不会出现2 1这种情况

现在子问题变为 到第k个硬币 合成金额i的组合数

状态转移为dp[k] [i] = dp[k - 1] [i] + dp[k] [i - coins[k]] (i > coins[k])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for (int i = 0; i < coins.size(); i++)
{
	dp[i][0] = 1;
}
for (int k = 0; k < coins.size(); k++)
{
    for (int i = 1; i <= amount; i++)
    {
        if (i >= coins[k - 1])
            dp[k][i] = dp[k][i - coins[k - 1]] + dp[k - 1][i];
        else
        {
            dp[k][i] = dp[k - 1][i];
        }
    }
}

此时就算交换两个for循环的顺序也不会影响结果 因为交换后子数组的状态转移方程不变 得到的结果也不变

如果要降成一维的数组 重新定义子问题为 必须选择第k个硬币的时候 凑成金额i的方案数 不能交换for循环的顺序 因为交换完之后 子问题的意义就是 对于金额i 有几种选择硬币的方案数（理解两个子问题的差别 一个是可重复一个不行）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int change(int amount, vector<int>& coins) 
    {
        vector<int>dp(amount + 1, 0); // dp[i] 表示必须选择第i个硬币时能凑成的金额的组合数
        dp[0] = 1;

        for (auto x: coins)
        {
            for (int i = 0; i <= amount; i++)
            {
                if (i >= x)
                dp[i] += dp[i - x];
            }
        }
        for (int i = 0; i <= amount; i++)
        {
            cout<<dp[i]<<" ";
        }
        return dp[amount];
    }
};

排列型背包

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) 
    {
        //dp[i] 表示到i为止的最小硬币数
        if (amount == 0)return 0;
        int n = coins.size();
        vector<int>dp(amount + 1, 1e9);
        for (auto x:coins)
        {
            if (x <= amount)
            dp[x] = 1;
        }
        for (int i = 0; i <= amount; i++)
        {
            for (auto x: coins)
            {
                if (i >= x)
                    dp[i] = min(dp[i - x] + 1, dp[i]);
            }
        }
        return dp[amount] == 1e9 ? -1 : dp[amount];
    }
};

279. 完全平方数 - 力扣（LeetCode）

背包问题 i 表示到i要多少数

当i > j ^2 的时候i 就可以更新 找到最少的次数 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def numSquares(self, n: int) -> int:
        num = 0
        for num in range(n):
            if num ** 2 > n:
                break
            elif num ** 2 == n:
                return 1
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            minn = inf
            j = 1
            while j ** 2 <= i:
                minn = min(minn, dp[i - j ** 2])
                j += 1
            dp[i] = minn + 1
        return dp[n]

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

二维

k 表示前k个硬币 i 表示凑成i 元

前k个硬币凑成i元的种类为 前k - 1个凑成i 元 加上 前k个硬币凑成了i - k元 就差k了

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        n = len(coins)
        dp = [[0] * (amount + 1) for _ in range(n + 1)]
        for k in range(n + 1):
            dp[k][0] = 1
        
        for k in range(1, n + 1):
            for i in range(1, amount + 1):
                if i >= coins[k - 1]:
                    dp[k][i] = dp[k][i - coins[k - 1]] + dp[k - 1][i]

定差型

不是 i - 1 和i 的关系 而是 每次比较 i 和i - nums[i] 这样的 某个差值nums[i] 之间的关系

1218. 最长定差子序列 - 力扣（LeetCode）

每次到达dp[i] 的时候 就去 dp[i - difference] 找上一个相差difference的

1
2
3
4
5
6
7
8
class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        dp = defaultdict(int)

        for x in arr:
            dp[x] = dp[x - difference] + 1
        
        return max(dp.values())

1027. 最长等差数列 - 力扣（LeetCode）

与上题相同 但是difference需要自己找

每个dp[i] 存储一个哈希表

每个哈希表存储 i - 1 ~ 0 的所有数 和nums[i] 的差值（key）和这个差值d 的出现的次数

比如9 4 7 2 10 到10 的时候 就往前找 2与10 差8 公差为8 的就是1个 再在2中找 公差为8的次数 0 ＋1=1

7 与10 差3 公差为3 在7中找公差为3的 为1 （7 和4） 总次数为2

最后个数是次数+1

1
2
3
4
5
6
7
8
9
10
class Solution:
    def longestArithSeqLength(self, nums: List[int]) -> int:
        dp = [{} for i in range(n)]
        for i in range(n):
            for j in range(i - 1, -1, -1):
               	d = nums[i] - nums[j]
                if d not in dp[i]:
                    dp[i][d] = dp[j].get(d, 1) + 1
                    
        return max(max(d.values()) for d in dp[1:])

Problem - E - Codeforces

从n向前寻找 当i + nums[i] <= n的时候 是可以形成 [长度+数组]的形式的 这时候就要检查这个地方是否需要选（可以选 也可以不选）

就要判断选这个点的代价（因为选这个可能影响其他代价更小的点）选了就是 dp[i + nums[i] + 1] 就是 这个点清除掉之后 比如

1
2
1 2 3 4 5 6 7
3 3 4 5 2 6 1

选了nums[1]的话 从1到n的代价就为 nums[5]的代价 因为1~4都被消除了

如果不选i 的话 那就是dp[i + 1] + 1(即直接删除这个点)

如果i + nums[i] > n 不能形成 数组 那就需要删除 删除的话就是dp[i] = dp[i + 1] + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using PII = pair<int, int>;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define endl '\n'

#define debug(x)                          \
    {                                     \
        cerr << #x << " = " << x << endl; \
    }
#define debugfull(x)                                                      \
    {                                                                     \
        cerr << #x << " = " << x << " (line " << __LINE__ << ")" << endl; \
    }

/*-------------------------------------------*/
const int N = 2e5 + 10;
void solve()
{
    int n;
    cin >> n;
    vector<int> nums(N), dp(n + 5, 0);
    for (int i = 1; i <= n; i++)
    {
        cin >> nums[i];
    }

    dp[n] = 1;
    for (int i = n - 1; i > 0; i--)
    {
        if (nums[i] + i > n)
            dp[i] = dp[i + 1] + 1;
        else
            dp[i] = min(dp[i + 1] + 1, dp[i + nums[i] + 1]);
    }
    cout << dp[1] << endl;
}
int main()
{
    // clock_t st = clock(), ed;
    ios::sync_with_stdio(0);
    cin.tie(0);
    // cout << setprecision(15) << fixed;
    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }

    // ed = clock();
    // double endtime = (double)(ed - st) / CLOCKS_PER_SEC;
    // cout << "Total time: " << endtime << endl;
    return 0;
}

100133. 购买水果需要的最少金币数 - 力扣（LeetCode）

跟上面那题有点像。。但是也不一样

找买水果的最少的钱数 首先写递归

这个水果买或不买 怎么看 哪些水果是免费的？ 从1开始递归往后找

能够不花钱的水果就是i + 1, i + 2 …, 2 * i

那我下一个要买的水果 就是从i + 1 i + 2… 2 * i + 1 因为2 * i + 1必定是要买的 而前面i个是可以选择买的 那么下一个买的肯定就在这中间

那么dfs（i）的意义就是 从1到后面需要花的最少的钱

那么从i开始 后面要花的最少的钱 就是 我现在买了i的钱 再加上下一个要买的 j 的最小值 （从j 到后面需要花的最少的钱）就是 i买的覆盖了i到2 * i 然后加上 dfs（j） 的最小值就是dfs(i)

然后递归出口 大于n的时候就是 0 就是不用在花钱了

细节地方是 prices 下标从1开始 我们dfs也定义从1开始 但是本质上prices是个数组 下标从0开始 所以每次加的时候 加prices[i - 1]

1
2
3
4
5
6
7
8
9
10
class Solution:
    def minimumCoins(self, prices: List[int]) -> int:
        n = len(prices)
        @cache
        def dfs(i):
            if i > n:
                return 0
            res = min(dfs(j) for j in range(i + 1, 2 * i + 2))
            return res + prices[i - 1]
        return dfs(1)

优化可以是 2 * i > n的时候 return prices[i - 1] 因为这时候只用花一次钱就行了

1
2
3
4
5
6
7
8
9
10
class Solution:
    def minimumCoins(self, prices: List[int]) -> int:
        n = len(prices)
        @cache
        def dfs(i):
            if 2 * i >= n:
                return prices[i - 1]
            res = min(dfs(j) for j in range(i + 1, 2 * i + 2))
            return res + prices[i - 1]
        return dfs(1)

然后翻译成递推 因为我们是从1开始到n的 那么变成递推就要改成从n 开始 因为从1 开始 递归到n 说明我实际上是从n算到1的 就是 我算前面的时候 后面是已经先算出来的

1
2
3
4
5
6
7
8
9
10
class Solution:
    def minimumCoins(self, prices: List[int]) -> int:
        n = len(prices)
        f = [0] * (n + 1)
        for i in range(n, 0, -1):
            if 2 * i >= n:
                f[i] = prices[i - 1]
            else:
                f[i] = prices[i - 1] + min(f[i + 1: 2 * i + 2])
        return f[1]

1214. 波动数列 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
int n, s, a, b;
const int mod = 100000007;
int f[1010][1010];
int getmod(int x, int y)
{
    return (x % y + y) % y;
}

int main()
{
    cin>>n>>s>>a>>b;
    f[0][0] = 1;
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            f[i][j] = ((f[i - 1][getmod(j - a * (n - i), n)] + f[i - 1][getmod(j + b * (n - i), n)]))%mod;
        }
    }
    cout<<f[n - 1][getmod(s, n)];
}

[d]:

algorithm
#algorithm #Ans #DP
动态规划
https://brtulien.github.io/2023/10/23/动态规划/
作者
Brtulien
发布于
2023年10月23日
更新于
2024年7月1日
许可协议