代码随想录算法训练营第34天| 动态规划：01背包理论基础（二维和一维）、416. 分割等和子集

模板：

• 今日学习的文章链接和视频链接
• 自己看到题目的第一想法
• 看完代码随想录之后的想法 
• 自己实现过程中遇到哪些困难 
• 今日收获，记录一下自己的学习时长

---

动态规划：01背包理论基础

题目链接：46. 携带研究材料（第六期模拟笔试）

学习链接：代码随想录

题解：

法一：

def fun():s = input().split()m = int(s[0])n = int(s[1])weight = list(map(int,input().split()))value= list(map(int,input().split()))dp = [[0]*(n+1) for _ in range(m)]for i in range(m):dp[i][0] = 0for j in range(1,n+1):if j >= weight[0]:dp[0][j]= value[0]else:dp[0][j]= 0for i in range(1,m):for j in range(1,n+1):if j < weight[i]:dp[i][j] = dp[i-1][j]else:dp[i][j] = max(dp[i-1][j],value[i]+dp[i-1][j-weight[i]])return dp[m-1][n]print(fun())

梳理一下还是挺有意思的

---

动态规划：01背包理论基础（滚动数组）

题目链接：46. 携带研究材料（第六期模拟笔试）

学习链接：代码随想录

题解：

法一：

def fun():s = input().split()m = int(s[0])n = int(s[1])weight = list(map(int,input().split()))value= list(map(int,input().split()))dp = [0]*(n+1)for j in range(n+1):dp[j] = 0for i in range(m):for j in range(n,0,-1):if j < weight[i]:dp[j] = dp[j]else:dp[j] = max(dp[j],value[i]+dp[j-weight[i]])return dp[n]print(fun())

正序和倒序的区别

---

416. 分割等和子集

题目链接：​​​​​​​416. 分割等和子集 - 力扣（LeetCode）

学习链接：​​​​​​​代码随想录

题解：

法一：

class Solution:def canPartition(self, nums: List[int]) -> bool:# 用二维写 空间复杂度很高s = sum(nums)if s % 2 != 0:return Falseelse:n = s//2m = len(nums)dp = [[0]*(n+1) for _ in range(m)]for i in range(m):dp[i][0] = 0for j in range(1,n+1):if nums[0] <= j:dp[0][j] = nums[0]else:dp[0][j] = 0for i in range(1,m):for j in range(1,n+1):if j < nums[i]:dp[i][j] = dp[i-1][j]else:dp[i][j] = max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i])return dp[m-1][n] == n

注意边界 nums的边界有点问题 可以思考一下

以及一维的解法。