本文主要是介绍算法题day44（补5.30日卡：动态规划04），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、刷题：今天继续学习动态规划01背包问题：
1.leetcode题目 1049. 最后一块石头的重量 II - 力扣（LeetCode）（medium)
解决：
class Solution:def lastStoneWeightII(self, stones: List[int]) -> int:target = sum(stones)//2dp = [0]*(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 sum(stones) - dp[target] - dp[target]2.leetcode题目 494. 目标和 - 力扣（LeetCode）(medium）
解决：
class Solution:def findTargetSumWays(self, nums: List[int], target: int) -> int:summ = sum(nums)bagsize = (summ + target)//2dp = [0]*(bagsize + 1)if summ<abs(target):return 0if (summ + target)%2 == 1:return 0dp[0] = 1for num in nums:for j in range(bagsize, num-1,-1):dp[j] += dp[j-num]return dp[bagsize]3.leetcode题目 474. 一和零 - 力扣（LeetCode）(medium）：
解决：
class Solution:def findMaxForm(self, strs: List[str], m: int, n: int) -> int:dp = [[0]*(n+1) for _ in range(m+1)]for s in strs:zero = s.count('0')one = len(s) - zerofor 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[m][n]总结：
这篇关于算法题day44（补5.30日卡：动态规划04）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
