代码随想录算法训练营第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] = 0
        
    for j in range(1,n+1):
        if j >= weight[0]:
            dp[0][j]= value[0]
        else:
            dp[0][j]= 0
            
    for 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] = 0
                
    for 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 False
        else:
            n = s//2
        m = len(nums)
        dp = [[0]*(n+1) for _ in range(m)]
        for i in range(m):
            dp[i][0] = 0
        for j in range(1,n+1):
            if nums[0] <= j:
                dp[0][j] = nums[0]
            else:
                dp[0][j] = 0
        for 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的边界有点问题 可以思考一下

以及一维的解法。