[数据结构与算法]01背包问题-动态规划

分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

分析：实际上是在数组nums中取一些数,它们的和等于target（即sum(nums)//2）。
设置状态：dp[i][j]表示nums从[0]到[i]中存在一些数和为j （i从0到len(nums)-1,j从0到target）
状态转移：
当nums[i]>target，必不能取nums[i]，dp[i][j] = dp[i-1][j]
当nums[i]<=target，可能不取nums[i]，可能取，有一种情况成立则dp[i][j]成立， dp[i][j]= dp[i-1][j] or dp[i-1][j-nums[i]]
初始化：。。。

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        all = sum(nums)
        maxnum = max(nums)
        if all%2!=0 or len(nums)==1:
            return False
        target = int(all/2)
        # print(target)
        if maxnum > target:
            return False
        dp = [[False]*(target+1) for _ in range(len(nums))]
        for i in range(len(nums)):
            dp[i][0]=True
        dp[0][nums[0]]=True
        for i in range(len(nums)):
            for j in range(target+1):
                if nums[i]>target:
                    #不取nums[i]
                    dp[i][j] = dp[i-1][j]  
                else:
                    #不取nums[i]或取nums[i]
                    dp[i][j]= dp[i-1][j] or dp[i-1][j-nums[i]]  
        # print(dp)
        return dp[-1][-1] 

目标和

给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

问题转化：假设满足条件的表达式中，前面为正号的数字和为p，前面为负号的数字和为n，有p-n=target,p+n=sum(nums),所以p=(target+sum)/2,此时问题转化为：数组nums中可以取出多少种不同的数字组合，满足和为(target+sum)/2的条件，(target+sum)/2成为了新的Target。

定义状态：dp[i][j]表示在数组nums的前i个数中选取元素，使得这些元素之和等于j的方案数。i从0到len(nums),j从0到Target+1
状态转移：
nums[i]>j时，必不取nums[i]: dp[i][j]=dp[i-1][j]
nums[i]<=j时,nums[i]可能不取也可能取，两种情况方案数应相加： dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]]

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

单词拆分

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp=[False]*(len(s)+1)
        dp[0]=True
        for i in range(1,len(s)+1):
            for j in range(0,i):
                if dp[j] and s[j:i] in wordDict:
                    dp[i]=True
                    break
        return dp[-1]

分析：
定义状态：dp[i]表示前i个字符是否可以被拆分为一个或多个在字典中出现的单词。
状态转移：若s[0:i]整个字符串都在Dict中，则dp[i]=True;
若不在，则设置j从0到i-1进行搜索，是否存在s的前j个字符可被拆分为Dict中出现的单词即dp[j]为True 且 s[j:i]在Dict中，若满足则dp[i]=True;（事实上当j=0时，就是在验证s[0:i]整个字符串是否都在Dict中，所以不必再单独拎出来做判断辽）
初始状态：dp[0]=True 空字符串在Dict中可被找到。