算法题day44（补5.30日卡：动态规划04）

本文主要是介绍算法题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）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---