上海微信网站公司,iis网站发布默认首页,邯郸房产网最新楼盘,nginx wordpress conf1049. 最后一块石头的重量 II 本题就和 昨天的 416. 分割等和子集 很像了#xff0c;可以尝试先自己思考做一做。 视频讲解#xff1a;动态规划之背包问题#xff0c;这个背包最多能装多少#xff1f;LeetCode#xff1a;1049.最后一块石头的重量II_哔哩哔哩_bilibili 代…1049. 最后一块石头的重量 II 本题就和 昨天的 416. 分割等和子集 很像了可以尝试先自己思考做一做。 视频讲解动态规划之背包问题这个背包最多能装多少LeetCode1049.最后一块石头的重量II_哔哩哔哩_bilibili 代码随想录 class Solution(object):def lastStoneWeightII(self, stones):totalsum(stones)dp[0]*(total1) #表示背包总量为i的最大价值targettotal//2for stone in stones:for i in range(target,stone-1,-1):dp[i]max(dp[i],dp[i-stone]stone)return total-dp[target]*2 总结 开始看到这道题是一点思路都没有只知道把公式套上去先试试但最终还是不行。看答案才知道我第一步分成两个差不多的部分这一步都不知道怎么可能写得出来。还一直担心背包问题不太清楚结果常识就不知道。不过这一维的背包确实要多练练二维的话之后二刷的时候再来看。 494. 目标和 大家重点理解 递推公式dp[j] dp[j - nums[i]]这个公式后面的提问 我们还会用到。 视频讲解动态规划之背包问题装满背包有多少种方法| LeetCode494.目标和_哔哩哔哩_bilibili 代码随想录 回溯法 class Solution(object):def findTargetSumWays(self, nums, target):totalsum(nums)if totaltarget:return 0if (totaltarget)%2!0:return 0result[]target(totaltarget)//2nums.sort()self.backtracking(nums,target,0,0,[],result)return len(result)def backtracking(self,nums,target,startindex,total,path,result):if totaltarget:result.append(path[:])for i in range(startindex,len(nums)):if totalnums[i]target:breaktotalnums[i]path.append(nums[i])self.backtracking(nums,target,i1,total,path,result)total-nums[i]path.pop() 总结 我想先用回溯法练练手因为回溯的路径只能保存加法或减法的数组所以不知道如何相加。但答案直接是先令都为加再在这上面进行减的操作把一个加改成减相当于减去两倍的数所以把target变成平均数。 01背包法 class Solution(object):def findTargetSumWays(self, nums, target):totalsum(nums)if totalabs(target):return 0if (totaltarget)%21:return 0target_sum(totaltarget)//2dp[0]*(target_sum1)dp[0]1for num in nums:for j in range(target_sum,num-1,-1):dp[j]dp[j-num]return dp[target_sum] 总结 dp[0]1我是想不到的原来初始化也有难的。这里的target也是求得平均值感觉01背包也不能算减法这里的背包即是价值也是体积跟上一题一样。abs函数代表的是绝对值。 01背包法 class Solution(object):def findMaxForm(self, strs, m, n):dp [[0] * (n 1) for _ in range(m 1)]for num in strs:zeroNum num.count(0) # 统计0的个数oneNum len(num) - zeroNum # 统计1的个数for i in range(m,zeroNum-1,-1):for j in range(n,oneNum-1,-1):dp[i][j]max(dp[i][j],dp[i-zeroNum][j-oneNum]1) return dp[m][n] 总结 初始化对了公式对了遍历对了dp数组错了。我之前用了这么久的 dp[[0]*(n1)]*(m1)都没有问题结果这题就出了问题明明和 dp [[0] * (n 1) for _ in range(m 1)]得出来的列表都是一样的。
