leetcode刷题-动态规划04

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

leetcode题目链接
代码随想录文档讲解

思路：

思路逆天：
这里如果用最相近的重量的石头进行相撞，得到的重量最小，因此看能不能把石头堆分成两堆重量相似的，这里[2, 7, 4, 1, 8, 1]，总和为23，23//2= 11，可以把石头分成11和12，这样可得到相撞后剩余石头重量为1。
尽量把石头分成重量总和近似相等的两堆。

1. dp[j]数组的含义：装满容量为j的背包的最大重量为dp[j]
2. dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])
3. 初始化，0, dp数组定义1501大小的就够了（30✖️100）/2
4. 遍历顺序

python代码：

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        target = sum(stones)//2
        dp = [0] * 1501
        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])
        result = abs(sum(stones) - dp[target] - dp[target])
        return result

494. 目标和（这个题好难）

leetcode题目链接
代码随想录文档讲解

思路：

回溯算法，如组合总和

动态规划法：
将数组分为加法集合（left）和减法集合（right），满足：left+right=sum, left-right=target
可得：left=(target+sum)/2，如果不能整除，说明凑不出target
有几种组合就是看正数（或负数）的集合有几种构成组合

1. dp[i[[j]数组的含义：使用nums数组中的[0,i]凑满容量为j的包有dp[i][j]种方法

2. 递推公式：dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
   （例如，dp[2][2] = dp[1][2] + dp[1][1]（不放物品2，用物品0和物品1填满容量为2的包；放物品2，因为物品2的容量为1，就是用物品0和物品1填满容量为1的包）
   考虑到 j-nums[i]可能会小于0，得到最终递推公式：
   if (nums[i] > j) dp[i][j] = dp[i - 1][j];
   else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];

3. 初始化：最上行和最左列，
   那么最上行dp[0][j] 如何初始化呢？dp[0][j]：只放物品0， 把容量为j的背包填满有几种方法。只有背包容量为 物品0 的容量的时候，方法为1，正好装满。其他情况下，要不是装不满，要不是装不下。所以初始化：dp[0][nums[0]] = 1 ，其他均为0 。
   表格最左列也要初始化，dp[i][0] : 背包容量为0， 放物品0 到 物品i，装满有几种方法。都是有一种方法，就是放0件物品。即 dp[i][0] = 1但这里有例外，就是如果 物品数值就是0呢？如果有两个物品，物品0为0， 物品1为0，装满背包容量为0的方法有几种。放0件物品，放物品0，放物品1，放物品0 和 物品1，此时是有4种方法。其实就是算数组里有t个0，然后按照组合数量求，即 2^t 。

4. 遍历顺序，都可

python代码：

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        # 这里保证了sum + target一定是大于等于零的，也就是left大于等于零（毕竟我们定义left大于right）
        if abs(target) > sum(nums) or (sum(nums)+target)%2 == 1:
            return 0
        target_sum = (sum(nums) + target)//2
        dp = [[0]*(target_sum+1) for _ in range(len(nums)+1)]
        
        dp[0][0] = 1
        for i in range(1, len(nums)+1):
            for j in range(target_sum+1):
                dp[i][j] = dp[i-1][j]
                if nums[i-1] <= j:
                    dp[i][j] += dp[i-1][j-nums[i-1]]
        return dp[len(nums)][target_sum]

474.一和零（二维dp）

leetcode题目链接
代码随想录文档讲解

思路：
之前的背包问题有一个维度，重量。此题中有两个维度：0的数量和1的数量

1. dp[i][j]，包含i个0j个1最多包含物品的数量，最终结果返回dp[m][n]
2. 递推公式：dp[i][j] = max(dp[i][j], dp[i-x][j-y]+1)
3. 初始化：dp[0][0] = 0, 其余初始化为一个最小的正整数0
4. 遍历顺序：先遍历物品再遍历背包，同时背包要逆序遍历

python代码：

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0]*(n+1) for _ in range(m+1)] # 注意初始化的时候先是n后是m
        for string in strs:
            x, y = 0, 0
            for char in string:
                if int(char) == 0:
                    x += 1
                else:
                    y += 1
            for i in range(m, x-1, -1):
                for j in range(n, y-1, -1):
                    dp[i][j] = max(dp[i][j], dp[i-x][j-y]+1)
        return dp[m][n]