Skip to content
蓝桥杯python基础练习-动态规划

内容源自灵神的基础算法精讲系列

温故而知新,蓝桥杯前复习一下


重点

如果能够找到与原问题相似的子问题,我们就能用递归解决

选/不选 以及 选那些的思路去缩小问题的范围

而所谓DP,本质上就是带备忘录的递归算法

要注意: dpi的定义是一些元素算得的结果

一些变化

对于回溯,通常是在「递」的过程中增量地构建答案,并在失败时能够回退,例如八皇后。对于递归,是把原问题分解为若干个相似的子问题,通常会在「归」的过程中有一些计算。如果一个递归能考虑用记忆化来优化,就需要 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]