第43天|dp

今天的题都是0-1背包的变种题

1049. Last Stone Weight II

0-1 背包问题,dp[j]仍然为到j为止能最大装多少.本题的最终结果为s=2dp[-1]这是因为题目是两个石头相撞,所以就是求一半的值dp[-1]然后对撞另一半s-dp[-1]就行了

当j为0时,没有石头可装,所以dp[0]=0

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        s=sum(stones)
        target=s//2
        dp=[0 for _ in range(target+1)]
        for i in range(len(stones)):
            for j in range(target,stones[i]-1,-1):
                dp[j]=max(dp[j],dp[j-stones[i]]+stones[i])
        return s-2*dp[-1]

494. Target Sum

0-1背包变种. dp[j]代表的是组成j能有多少种方法. 我们知道x-(sum-x)=target 也即是说 x=(s+target)//2是正数的和,那我们只要找到组成正数和有最多有多少种方法就可以了.那么dp[j]代表的就是对于每个num所对应的dp[j]的和

当j=0时,至少有1种方法,所以dp[0]=1

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        s=sum(nums)
        if s<abs(target) or (s+target)%2==1:
            return 0
        bag=(target+s)//2
        dp=[0 for _ in range(bag+1)]
        dp[0]=1
        for i in range(len(nums)):
            for j in range(bag,nums[i]-1,-1):
                dp[j]+=dp[j-nums[i]]
        return dp[-1]

474. Ones and Zeroes

0-1背包问题.但是dp[i][j]为到i个0j个1为止最多有多少个string.那递推公式就是dp[i][j]=max(dp[i][j],dp[i-zero][j-one]+1).

递归顺序上还是从后到前且两层都是从后到前

初值dp[0][0]=0因为没有0和1时也没有string

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp=[[0 for _ in range(n+1)] for _ in range(m+1)]
        for st in strs:
            one=st.count('1')
            zero=st.count('0')
            for i in range(m,zero-1,-1):
                for j in range(n,one-1,-1):
                    dp[i][j]=max(dp[i][j],dp[i-zero][j-one]+1)
        return dp[-1][-1]