内容源自灵神的基础算法精讲系列
温故而知新,蓝桥杯前复习一下
重点
如果能够找到与原问题相似的子问题,我们就能用递归解决
选/不选 以及 选那些的思路去缩小问题的范围
而所谓DP,本质上就是带备忘录的递归算法
要注意:
一些变化
对于回溯,通常是在「递」的过程中增量地构建答案,并在失败时能够回退,例如八皇后。对于递归,是把原问题分解为若干个相似的子问题,通常会在「归」的过程中有一些计算。如果一个递归能考虑用记忆化来优化,就需要 return 一个值并加以保存。
时间复杂度计算: 状态个数*单个状态所需的时间
转为递推?
- 确定边界
- 自树底向上
为什么要转为dp?
两者可视为手动挡和自动挡,自动挡虽然方便,但是灵活性不如手动挡(递推dp)
比如递推形式可以滚动数组优化,可以加入各种各样的数据结构优化
例题
py
class Solution:
def rob(self, nums: List[int]) -> int:
@cache
def f(i):
if i<0:
return 0
return max(f(i-1),f(i-2)+nums[i])
return f(len(nums)-1)
py
class Solution:
def rob(self, nums: List[int]) -> int:
f=[0]*(len(nums)+2)
for i,v in enumerate(nums):
f[i+2]=max(f[i+1],f[i]+v)
return f[-1]
py
class Solution:
def rob(self, nums: List[int]) -> int:
a=b=0
for i,v in enumerate(nums):
c=max(b,a+v)
a=b
b=c
return b
练习
70. 爬楼梯
py
class Solution:
def climbStairs(self, n: int) -> int:
# @cache
# def f(i):
# if i==0:
# return 1
# if i<0:
# return 0
# return f(i-1)+f(i-2)
# return f(n)
# 转移 f(i+2)=f(i+1)+f(i)
# f=[0]*(n+2)
# f[1]=1
# for i in range(n):
# f[i+2]=f[i+1]+f[i]
# return f[-1]
a,b=0,1
for i in range(n):
c=a+b
a=b
b=c
return b
746. 使用最小花费爬楼梯
py
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
"""
f(i)=min(f(i-1),f(i-2))+cost[i]
"""
cost.append(0)
f=[0]*(len(cost)+2)
for i,v in enumerate(cost):
f[i+2]=min(f[i+1],f[i])+cost[i]
return f[-1]
377. 组合总和
py
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
# @cache
# def f(i):
# if i<=0:
# return int(i==0)
# ret=0
# for j in nums:
# ret+=f(i-j)
# return ret
# return f(target)
f=[0]*(target+1)
f[0]=1
for i in range(target+1):
for v in nums:
if i<v: continue
f[i]+=f[i-v]
return f[-1]
2466. 统计构造好字符串的方案数
有意思的题,要发现贡献本质
错误写法
py
class Solution:
def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
MOD=int(1e9)+7
@cache
def f(s):
if len(s)>high:
return 0
res=int(low<=len(s)<=high)
return res+(f(s+"0"*zero)%MOD+f(s+"1"*one)%MOD)%MOD
return f("")
py
class Solution:
def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
MOD=int(1e9)+7
# f(i)=f(i-zero)+f(i-one)
# @cache
# def f(i):
# if i<=0:
# return int(i==0)
# return (f(i-zero)%MOD+f(i-one)%MOD)%MOD
# s=0
# for i in range(low,high+1):
# s+=f(i)%MOD
# s%=MOD
# return s
f=[0]*(high+1)
f[0]=1
res=0
for i in range(1,high+1):
ans=0
if i-zero>=0:
ans+=f[i-zero]%MOD
ans%=MOD
if i-one>=0:
ans+=f[i-one]%MOD
ans%=MOD
f[i]=ans
if i>=low:
res+=f[i]%MOD
res%=MOD
return res
740. 删除并获得点数
py
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
c={}
a=[]
for i in nums:
if i not in c.keys():
c[i]=1
a.append(i)
else:
c[i]+=1
a.sort()
# @cache
# def f(i):
# if i<0:
# return 0
# if i==0:
# return a[0]*c[a[0]]
# ans=f(i-1)
# if a[i]==a[i-1]+1:
# ans=max(ans,f(i-2)+a[i]*c[a[i]])
# else:
# ans=max(ans,f(i-1)+a[i]*c[a[i]])
# return ans
# # print(a,f(2))
# return f(len(a)-1)
f=[0]*len(a)
f[0]=a[0]*c[a[0]]
for i in range(1,len(a)):
ans=f[i-1]
if a[i]==a[i-1]+1:
if i-2>=0:
ans=max(ans,f[i-2]+a[i]*c[a[i]])
else:
ans=max(ans,a[i]*c[a[i]])
else:
ans=max(ans,f[i-1]+a[i]*c[a[i]])
f[i]=ans
return f[-1]
2320. 统计放置房子的方式数
py
class Solution:
def countHousePlacements(self, n: int) -> int:
# f[i]=f[i-1]+1+f[i-2]
MOD=10**9+7
f=[0]*(n+2)
for i in range(n):
f[i+2]=(f[i+1]%MOD+1+f[i]%MOD)%MOD
return ((f[-1]+1)**2)%MOD
213. 打家劫舍 II
分类讨论拆环
py
class Solution:
def rob(self, nums: List[int]) -> int:
def rob1(a):
# f(x)=max(f(x-1),f(x-2)+a[x])
if len(a)==0:
return 0
x,y=0,0
for i in a:
x,y=max(x,y+i),x
return x
return max(rob1(nums[2:-1])+nums[0],rob1(nums[1:]))
LCR 166. 珠宝的最高价值
py
class Solution:
def jewelleryValue(self, frame: List[List[int]]) -> int:
n=len(frame)
m=len(frame[0])
# @lru_cache(maxsize=None)
# def f(i,j):
# if i>=n or j>=m:
# return 0
# return max(f(i+1,j),f(i,j+1))+frame[i][j]
# return f(0,0)
f=deepcopy(frame)
for i in range(n):
for j in range(m):
if i==0 and j==0:
continue
elif i==0:
f[i][j]+=f[i][j-1]
elif j==0:
f[i][j]+=f[i-1][j]
else:
f[i][j]+=max(f[i-1][j],f[i][j-1])
return f[-1][-1]