Leetcode刷题第十二天-动态规划

1049：最后一块石头的重量II

链接：1049. 最后一块石头的重量 II - 力扣（LeetCode）

 1 class Solution:
 2     def lastStoneWeightII(self, stones: List[int]) -> int:
 3         #dp[i]背包为i的最大价值为dp[i]
 4         #推导公式dp[i]=max(dp[i], dp[i-stones[i]]+stones[i])
 5         #dp数组初始化dp=[0]*1501
 6         #遍历顺序：背包倒序
 7         #打印dp数组
 8         sums=sum(stones)
 9         num=sums//2
10         dp=[0]*1501
11         for stone in stones:
12             for i in range(num,stone-1,-1):
13                 dp[i]=max(dp[i],dp[i-stone]+stone)
14         return sums-2*dp[num]

494:目标和

链接：494. 目标和 - 力扣（LeetCode）

 1 class Solution:
 2     def findTargetSumWays(self, nums: List[int], target: int) -> int:
 3         #dp[i]背包为i装满i有dp[i]方法
 4         #推导公式dp[i]+=dp[i-nums[j]](j:0--len(nums))
 5         #dp数组初始化dp=[1]
 6         #遍历顺序：背包倒序
 7         #打印dp数组
 8         sums=sum(nums)
 9         if((sums+target)%2):    return 0
10         num=(sums+target)//2
11         dp=[0]*1001
12         dp[0]=1
13         for n in nums:
14             for i in range(num,n-1,-1):
15                 dp[i]+=dp[i-n]
16         return dp[num]

474:1和0

链接：474. 一和零 - 力扣（LeetCode）

 1 class Solution:
 2     def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
 3         #dp[i][j]背包为i,j最大价值
 4         #推导公式dp[i][j]=max(dp[i][j],dp[i-x][j-y]+1)
 5         #dp数组初始化dp=[1]
 6         #遍历顺序：倒序
 7         #打印dp数组
 8         dp=[[0 for i in range(n+1)] for j in range(m+1)]
 9         for s in strs:
10             x=s.count('0')
11             y=s.count('1')
12             for i in range(m,x-1,-1):
13                 for j in range(n,y-1,-1):
14                     dp[i][j]=max(dp[i][j],dp[i-x][j-y]+1)
15         return dp[m][n]

01背包最大价值推到公式：dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])，正序遍历

降低维度：dp[j] = max(dp[j], dp[j - w[i]] + v[i])，倒序遍历背包

01背包装满的方法个数：dp[i]+=dp[i-nums[j]](j:0--len(nums))，倒序

牛客跳台阶扩展

链接：跳台阶扩展问题_牛客题霸_牛客网 (nowcoder.com)

递推公式：dp[i] += dp[j]（j:0---i）

 1 import sys
 2 
 3 for line in sys.stdin:
 4     a = line.split()
 5     n = int(a[0])
 6     dp = [0] * (n + 1)
 7     if n < 3:
 8         print(n)
 9         break
10     dp[0], dp[1], dp[2] = 1, 1, 2
11     for i in range(3, n + 1):
12         for j in range(i):
13             dp[i] += dp[j]
14     print(dp[n])