【代码随想录】动态规划专题2（Python）_代码随想录 python

01背包问题：
题意：n种物品放进容量为m的包里，获得最大价值
二维dp数组解法：
- - - - dp[i][j]表示任取0-i种物品，放进容量为j的背包能获取的最大价值
- - - - dp[i][j] = max(没放i，放i ） 没放i = dp[i-1][j] 放i = dp[i-1][ j-重量[i] ] + 价值[i]
- - - - 首行首列为0
一维dp数组解法：
- - - - dp[i][j]只与上一层的dp[i-1][j]有关，所以重复利用一行数组即可
- - - - dp[j]表示放进容量为j的背包能获取的最大价值
- - - - dp[j] = max(没放i，放i ） 没放i = dp[j] 放i = dp[ j-重量[i] ] + 价值[i]
- - - - 首个，即容量为0价值为0
- - - - 顺序，先物品(行)后背包(列)，背包逆序，原理画图

8.分割等和子集

416. 分割等和子集
题意：01背包，共i个物品能否装满容量为j的背包
dp[j]表示在前i个物品中任取，装入容量为j的背包的最大价值，重量与价值大小相同
dp[0]=0，背包容量最大为物品重量总和的一半，最小为第i个物品的重量

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total_sum = sum(nums)
        if total_sum%2: return False
        dp = [0]*(total_sum//2+1)
        for i in range(len(nums)):
            for j in range(total_sum//2,nums[i]-1,-1):
                dp[j] = max(dp[j],dp[j-nums[i]]+nums[i])
        if dp[-1]==total_sum//2: return True
        return False
1
2
3
4
5
6
7
8
9
10

9.最后一块石头的重量II

1049.最后一块石头的重量II
题意：将石头分为尽可能均等的两份，求差
即，尽可能装满sum()//2的背包，重量=价值
返回值为sum-dp[-1]-dp[-1]

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        total_sum = sum(stones)
        dp = [0]*(total_sum//2+1)
        for i in range(len(stones)):
            for j in range(total_sum//2,stones[i]-1,-1):
                dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])
        return total_sum-dp[-1]-dp[-1]
1
2
3
4
5
6
7
8

10.目标和

494.目标和
题意：分两份，一份正值一份负值，装满正值的背包有多少种方法
left-right=target,left+right=sum -> left=(sum+target)/2 正值
dp[j]表示装满容量为j的背包有多少种方法
dp[j] += dp[j-num]
dp[0] = 1

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total_sum = sum(nums)
        if abs(target)>total_sum: return False
        if (total_sum+target)%2: return False
        left = (total_sum+target)//2
        dp = [0]*(left+1)
        dp[0] = 1
        for i in nums:
            for j in range(left,i-1,-1):
                dp[j] += dp[j-i]
        return dp[-1]
1
2
3
4
5
6
7
8
9
10
11
12

11.一和零

474.一和零
两个维度的01背包
价值为1
dp[i][j]表示背包容量为i+j时的最大价值

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        x = [0]*len(strs)
        y = [0]*len(strs)
        for i in range(len(strs)):
            x[i] = strs[i].count('0')
            y[i] = len(strs[i])-x[i]
        for ii in range(len(strs)):
            for i in range(m,x[ii]-1,-1):
                for j in range(n,y[ii]-1,-1):
                    dp[i][j] = max(dp[i][j], dp[i-x[ii]][j-y[ii]]+1)
        return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13

完全背包问题：
题意：n种物品放进容量为m的包里，获得最大价值，物品取用次数不限
二维dp数组解法：
- - - - 01背包为倒序遍历，完全背包为正序遍历
- - - - 先物品后背包为组合，先背包后物品为顺序
一维dp数组解法：
- - - - dp[i][j]只与上一层的dp[i-1][j]有关，所以重复利用一行数组即可
- - - - j是 [物品[i],背包最大容量+1]
- - - - dp[j] += dp[j-coins[i]]

12.零钱兑换II

518.零钱兑换II

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0]*(amount+1)
        dp[0] = 1
        for i in range(len(coins)):
            for j in range(coins[i],amount+1):
                dp[j] += dp[j-coins[i]]
        return dp[-1]
1
2
3
4
5
6
7
8

13.组合总和 Ⅳ

377. 组合总和 Ⅳ
非组合，有顺序

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

14.零钱兑换

322. 零钱兑换
背包容量为[0,amount+1)
背包容量为0时最少需要0个物品
与顺序无关，所以先物品再背包
物品的范围为[0,物品种类+1)，背包范围为[物品[i],amount+1)
dp[j] = min(dp[j],dp[j-物品[i]]+1)

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [sys.maxsize]*(amount+1)
        dp[0] = 0
        for i in range(0,len(coins)):
            for j in range(coins[i],amount+1):
                if dp[j-coins[i]] != sys.maxsize:
                    dp[j] = min(dp[j],dp[j-coins[i]]+1)
        if dp[-1]==sys.maxsize: return -1
        return(dp[-1])
1
2
3
4
5
6
7
8
9
10

15.完全平方数

279.完全平方数
与上题相似

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [sys.maxsize]*(n+1)
        dp[0] = 0
        for i in range(1,n+1):
            for j in range(i*i,n+1):
                if dp[j-i*i]!=sys.maxsize:
                    dp[j] = min(dp[j],dp[j-i*i]+1)
        if dp[-1]==sys.maxsize: return -1
        return dp[-1]
1
2
3
4
5
6
7
8
9
10

16.单词拆分

139.单词拆分
背包容量为[0,len(s)+1)
物品集改为set，好找
dp[i]表示到长度i为止的字符串s是否符合要求
if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true
dp[0]=True
有顺序，先遍历背包

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wordDict = set(wordDict)
        dp = [False]*(len(s)+1)
        dp[0] = True
        for i in range(1,len(s)+1):
            for j in range(i):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
                    break
        return dp[-1]
1
2
3
4
5
6
7
8
9
10
11