第四十六天|dp

今天的题还是完全背包的题

139. Word Break

这道题其实用deque也能做,但是需要@cache去记录之前尝试过的值,.相对简单的办法就是用完全背包了

这道题worddict就是物品.我们的dp[i]代表到i为止是不是能满足题意分成segmentation

处置化全为false,但是dp[0]=True.这是因为为0时是满足6题意的划分成0个segmentation.

递推公式要满足两点一个是dp[i]=dp[i]: 这种情况是看所有的word情况,找出是否有true的可能行.另一点是or (dp[i-len(w)] and w==s[i-len(w):i]),表明当当前i到j能组成一个word且之前的已经满足segmentation的要求

本题是找排列,所以遍历先背包后物品

class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:dp=[False for _ in range(len(s)+1)]dp[0]=Truefor i in range(len(s)+1):for w in wordDict:dp[i]=dp[i] or (dp[i-len(w)] and w==s[i-len(w):i])return dp[-1]

dp总结:

总的来说dp很难,但是都是背包问题: 即重量为w的背包能装下的物品的最大价值为多少.背包问题可以分成两种,一种是0-1背包一种是完全背包, 区别在于0-1背包每个物品只能取一次,完全背包可以用多次.

dp的五部曲包括:1. 确认dp含义.2.确认递推公式.3确认初值.4 确认遍历顺序.5 推导试一下

对于0-1背包而言,遍历的时候背包正序,物品倒序.完全背包则是全是正序.但是需要注意的点在于如果是求完全背包的排列问题则要先背包再物品遍历.如果是完全背包的组合问题则要先物品再背包遍历.

递推公式大致有这样几种:

问装满背包有几种方法：dp[j] += dp[j - nums[i]] 

问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j])

其他的就随缘了