1、最大连续子数组和
关键核心是累加和的正负：
2、零钱组合
1）最少硬币数
总钱数：总硬币数：动态规划迭代：
外部总硬币数：
内部总钱数：
自底向上迭代：
核心代码如下：
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for j in range(coin,amount+1):
dp[j] = min(dp[j], dp[j - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
零钱组合1
2）满足钱数的多少种组合数
外部总硬币数：
内部总钱数：
自底向上累加：
核心思路：
对于面额为coin 的硬币，当 coin≤i≤amount 时，如果存在一种硬币组合的金额之和等于 i −coin，则在该硬币组合中增加一个面额为 coin 的硬币，即可得到一种金额之和等于 i的硬币组合。因此需要遍历 coins，对于其中的每一种面额的硬币，更新数组 dp 中的每个大于或等于该面额的元素的值。
核心代码如下：
n=len(coins)
if amount==0 or n==0:
return 1
dp=[0]*(amount+1)
dp[0]=1
for coin in coins:
for j in range(coin,amount+1):
dp[j]=dp[j]+dp[j-coin]
return dp[amount]
3）组合总数
leetcode377
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
https://leetcode-cn.com/problems/combination-sum-iv/
dp=[0]*(target + 1)
dp[0] = 1
for i in range(1,target+1):
for num in nums:
if num <= i:
dp[i] += dp[i - num]
return dp[target]
3、01背包
总体积：总物品数：动态规划迭代：体积V
核心问题：
自顶向下不断递归迭代
核心代码：
if V<=0 or n<=0:
return 0
dp=[0 for i in range(V+1)]
for i in range(n):
vi=vw[i][0]
wi=vw[i][1]
for j in range(V,vi-1,-1):
dp[j]=max(dp[j-vi]+wi,dp[j])
return dp[V]
牛客网01背包问题：
https://www.nowcoder.com/practice/2820ea076d144b30806e72de5e5d4bbf?tpId=196&&tqId=37561&rp=1&ru=/activity/oj&qru=/ta/job-code-total/question-ranking
1）完全平方数
核心代码如下：
k=int(sqrt(n))
dp=[float('inf')]*(n+1)
dp[0]=0
dp[1]=1
for i in range(1,k+1):
tmp=i*i
for j in range(tmp,n+1):
dp[j]=min(dp[j],dp[j-tmp]+1)
return dp[n]
2）掷骰子的N种方法
leetcode1155
投掷骰子的方法数：d个骰子,每个有f个面(点数为1,2,...f),求骰子点数和为target的方法
分组0/1背包的组合问题：dp[i][j]表示投掷i个骰子点数和为j的方法数;三层循环：最外层为背包d,然后先遍历target后遍历点数f
应用二维拓展的转移方程3：dp[i][j]+=dp[i-1][j-f];
链接：https://leetcode-cn.com/problems/coin-change/solution/yi-pian-wen-zhang-chi-tou-bei-bao-wen-ti-sq9n/
3）最长递增子序列 leetcode300
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
1、贪心+二分查找
贪心：保持数组递增
二分查找：查找不满足大于数组最大值的位置，第一个小于原数组中元素
时间复杂度：o（nlogn)
空间复杂度：o（n)
核心代码：
n=len(nums)
l=[]
length=0
if n<=1:
return len(nums)
l.append(nums[0])
for i in range(1,n):
if nums[i]>l[-1]:
l.append(nums[i])
else:
#在数组中二分查找，找到第一个比 nums[i] 小的数，并更新 d[k + 1] = nums[i]。
k=len(l)
left=0
right=k-1
while left<=right:
mid=(left+right)//2
if l[mid]<nums[i]:
left=mid+1
else:
right=mid-1
l[left]=nums[i]
return len(l)
调用函数代码简单：
import bisect
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n=len(nums)
ls=[]
if n<=1:
return len(nums)
dp=[1 for i in range(n)]
ls.append(nums[0])
for i in range(n):
if nums[i]>ls[-1]:
ls.append(nums[i])
else:
tmp=bisect.bisect_left(ls,nums[i])
ls[tmp]=nums[i]
return len(ls)
2、动态规划
包含当前数组元素的上升子序列最大值，状态转移：dp[i]=max(dp[i],dp[i-j]+1),nums[i]>nums[j]
核心代码：
n=len(nums)
l=[]
if n<=1:
return len(nums)
dp=[1 for i in range(n)]
for i in range(n):
for j in range(i):
if nums[i]>nums[j]:
dp[i]=max(dp[i],dp[j]+1)
return max(dp)
https://leetcode-cn.com/problems/longest-increasing-subsequence/
3、字典序最长上升子序列
一共需要两个辅助数组和一个辅助变量：
dp数组：用来存储位置i对应的最长子序列的长度
end数组：用来存储长度为i的子序列的最后一个元素的最小值
len：用来记录当前找到的最长子序列的长度
最后产生字典序最小的：
核心代码如下：
import bisect
#bisect.bisect_left(ls,arr[i]),返回第一个小于arr[i]的索引
def LIS(self , arr ):
# write code here
if not arr:
return 0
n=len(arr)
dp = [1 for i in range(n)]
ls=[arr[0]]
res=[]
for i in range(1,n):
if arr[i] > ls[-1]:
ls.append(arr[i])
dp[i]=len(ls)
else:
tmp=bisect.bisect_left(ls,arr[i])
ls[tmp]=arr[i]
dp[i]=tmp+1
lls=len(ls)
res=[0]*lls
for i in range(n-1,-1,-1):
if dp[i]==lls:
res[lls-1]=arr[i]
lls=lls-1
return res
https://www.nowcoder.com/practice/9cf027bf54714ad889d4f30ff0ae5481?tpId=117&&tqId=37796&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking
4）最长回文串长度
动态规划节最长回文子串长度：
核心代码如下：
dp=[[False]*n for i in range(n)]
smax=0
for d in range(n):
for i in range(n-d):
j=i+d
if A[i]==A[j]:
if d==0 or d==1 or d==2:
dp[i][j]=True
else:
dp[i][j]=dp[i+1][j-1]
if dp[i][j]:
smax=max(smax,d+1)
return smax
5）股票交易（两次）
1、初始5个状态
2、状态转移
什么都不做，和前一天买入/卖出最大收益+当前操作
核心代码：
dp0[0]=0
dp1[0]=-prices[0]
dp2[0]=0
dp3[0]=-prices[0]
dp4[0]=0
for i in range(1,k):
dp0[i]=dp0[i-1]
dp1[i]=max(dp1[i-1],dp0[i-1]-prices[i])
dp2[i]=max(dp2[i-1],dp1[i-1]+prices[i])
dp3[i]=max(dp3[i-1],dp2[i-1]-prices[i])
dp4[i]=max(dp4[i-1],dp3[i-1]+prices[i])
return dp4[k-1]
动态规划总结：
https://leetcode-cn.com/problems/coin-change/solution/yi-pian-wen-zhang-chi-tou-bei-bao-wen-ti-sq9n/
网友评论