动态规划

发表于： 2025-02-12 分类于： Leetcode/dp

字数： 1959 阅读：≈ 4分钟

灵神题单

线性dp

lc 377: 与完全背包的不同点在于：[1,3],[3,1]被算作两个不同的答案。因此解法类似permutation型的回溯。如果用cache修饰 dfs, 则不能使用全局变量res来计算个数，必须把res作为 dfs的返回值。

LC 139: 单词拆分

leetcode可以通过leet和code组成。如果code在 wordSet中，那么dp[9]=dp[4]

House Robber

LC 198: 空间优化

LC 213 打家劫舍 II: 所有房子围成一圈。考虑只能偷前(n-1)个房子的情况，和只能偷后(n-1)个房子的情况

最大子数组和

LC 53:dp[i]存放以当前元素结尾的最大和

dp[i]=max(dp[i-1]+nums[i], nums[i])

空间优化：

1
2
f=max(x, f+x)
res=max(f, res)

LC 1749 任意子数组和的绝对值的最大值:

遍历过程中，保持一个以当前元素结尾的最大和与最小和。绝对值最大->子数组和最大或最小

网格图 DP

基础题只需要做：63. 不同路径 II

dp[i+1][j+1]表示遍历到grid[i][j]时的方案数。初始化时，只需要考虑dp[1]这一行的值

最长回文子串

dp[j][i]表示s[j:i+1]是否为回文。i从左往右遍历，j从i往左遍历。

01背包

lc 494

记忆化搜索：选恰好k个，使得容量恰好等于c，求方案数. 递推是从后往前，dp只不过是把递推改写成了从前往后遍历。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        s=sum(nums)
        p=(target+s)//2
        if (target+s)%2!=0:
            return 0

        @cache
        def dfs(i, c):
            if i<0:
                if c==0:
                    return 1 #代表一种方案成功
                return 0
            #如果容量不够
            if nums[i]>c:
                return dfs(i-1, c)
            return dfs(i-1, c)+dfs(i-1, c-nums[i])
        return dfs(len(nums)-1, p)

把这个翻译成 dp

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n=len(nums)
        s=sum(nums)
        p=(target+s)//2
        if (target+s)%2!=0 or target+s<0:
            return 0

        f=[[0]*(p+1) for _ in range(n+1)]
        f[0][0]=1
        for i, x in enumerate(nums):
            for c in range(p+1):
                if c>=x:
                    f[i+1][c]=f[i][c]+f[i][c-x]
                else:
                    f[i+1][c]=f[i][c]
        return f[n][p]

lc 3180

给你一个整数数组 rewardValues，长度为 n，代表奖励的值。最初，你的总奖励 x 为 0，所有下标都是未标记的。你可以执行以下操作任意次：

从区间 [0, n - 1] 中选择一个未标记的下标 i。如果 rewardValues[i] 大于你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并标记下标 i。以整数形式返回执行最优操作能够获得的最大总奖励。

dp[i][j]表示从前i个物品中，能否拿到和为j

完全背包

有 n个物品，第i个物品的体积为w[i], 价值为v[i]，每个物体能选无限次，容量为 capacity，求最大价值。

dfs(i, c)=dfs(i-1, c)+dfs(i, c-w[i])

LC 322 coin change

零钱价值视为体积，每个的价值为1. amount视为capacity，求体积恰好为capacity的时候，最小价值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def coinChange(self, coins: List[int], amount: int) -> int:
    #dfs(i, c)表示遍历到第 i个硬币的时候，当前总价值为 c，所需要的最少硬币数
    @cache
    def dfs(i, c):
        if i<0:
            return 0 if c==0 else inf #容量需恰好为 amount
        if coins[i]>c:
            return dfs(i-1, c)
        return min(dfs(i-1, c), dfs(i, c-coins[i])+1)
    res=dfs(len(coins)-1, amount)
    return res if res<inf else -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def coinChange(self, coins: List[int], amount: int) -> int:
    n=len(coins)
    dp=[[inf]*(amount+1) for _ in range(n+1)]
    dp[0][0]=0
    for i, x in enumerate(coins):
        for j in range(amount+1):
            if x<=j:
                dp[i+1][j]=min(dp[i+1][j-x]+1, dp[i][j])            
            else:
                dp[i+1][j]=dp[i][j]
    return dp[n][amount] if dp[n][amount]<inf else -1

最长公共子序列

LC 1143

dfs(i, j)表示遍历到s[i]和t[j]时，从前往后最长公共子序列的长度。

如果s[i]==t[j]，必须选当前字符

dfs(i, j)=dfs(i-1, j-1)+1;

如果s[i]!=t[j]

dfs(i, j)=max(dfs(i, j-1), dfs(i-1, j))

LC 72 编辑距离

dfs(i, j)表示遍历到s[i]和t[j]时，为保持两个字符串相同，所需要的操作数

s: rorse, t: rose

此处遍历到这两个字符不同，如果对 S 执行删除操作，相当于

dfs(i, j)=dfs(i-1, j)+1

s: ct, t: cat

如果此时对S执行添加操作，相当于

dfs(0, 0)=0, dfs(0, 1)=dfs(0, 0)+1=1

dfs(i, j)=dfs(i, j-1)+1

类似地，对 S 执行替换操作，相当于

dfs(i, j)=dfs(i-1, j-1)+1

当遍历到s[i]和t[j]时, 如果他们不相同，则需要遍历三种情况，看看当前字母前面的字母是什么样子的。所以，

dfs(i, j)=min(dfs(i-1, j), dfs(i, j-1), dfs(i-1, j-1))+1

💡注意边界条件。dp[0][0]=0, dp[i][0]=i, dp[0][j]=j. 初始化为(m+1)*(n+1)的矩阵，dp[i][j]表示遍历到word1的第i个和word2的第j个，也就是word1[i+1], word2[j+1]

LC 3290 最高乘法得分

a = [3,2,5,6], b = [2,-6,4,-5,-3,2,-7] 从 b的最后一个元素开始思考。

如果选它，那么考虑[3,2,5]和[2,-6,…,2]中间元素相乘的最大值。
如果不选它，那么考虑[3,2,5,6]和[2,-6,…,2]中间元素相乘的最大值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def maxScore(self, a: List[int], b: List[int]) -> int:
    #dp[i][j]=max(dp[i][j-1], dp[i-1][j-1]+a[i-1]*b[j-1])
    m=len(a)
    n=len(b)
    dp=[[-inf]*(n+1) for _ in range(m+1)]
    dp[0]=[0]*(n+1)
    for i in range(m):
        for j in range(n):
            dp[i+1][j+1]=max(dp[i+1][j], dp[i][j]+a[i]*b[j])
    return dp[m][n]
    #dp[1][2]=max(dp[1][1], dp[0][1]+a[0]*b[1])

初始化dp[0]=[0]*(n+1)，因为考虑到数组 a遍历到0（还没开始遍历的时候），不管b数组遍历到哪里，初始的乘积和为 0. 也可思考循环赋值过程，如最后一行的注释。

区间DP

状态转移方向：从中间到两边，i倒序遍历，j正序遍历

516. 最长回文子序列：选/不选

1
2
3
4
if s[i]==s[j]:
    dfs(i, j)=dfs(i+1, j-1)+2
else:
    dfs(i, j)=max(dfs(i+1, j), dfs(i, j-1))

注意递推的遍历顺序。

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

LC 5

dp[i][j]记录当前字符串是否为回文；
需要 start 变量记录字符串的开头

1039. 多边形三角剖分的最低得分

区间dp一定是从中间往两边蔓延。

1
dp[i][j]=values[i]*values[j]*values[k]+dp[i][k]+dp[k][j]

dp如何初始化？看递归的尽头是什么。
比如这题考虑i,k,j=0,1,2时，dp[i][k]必须为0. 所以所有dp[i][i+1]=0

最长递增子序列

回溯->记忆化搜索->动态规划
贪心+二分可实现最优