[数据结构与算法]Python 蓝桥杯 动态规划 2道例题+配套1道历年真题

距离蓝桥杯64天? 快和小郑一起准备蓝桥杯吧 ?

? ? ? ? 蓝桥杯真题题目链接：数字三角形

????????Leedcode青蛙跳台阶

????????Leedcode不同路径

?特此鸣谢这位作者的点播，小郑从中获益不少文章来源https://cloud.tencent.com/developer/article/1538177

青蛙跳台阶：(入门题)

?思路简单:解析见代码（虽然递归超时，思想值得学习）

class Solution:
    def numWays(self, n: int) -> int:
        #dp[n]    代表跳上第n个台阶有dp[n]种跳法
        #寻找递推关系 dp[n]=dp[n-1]+dp[n-2]
        #初值dp[0]=1,dp[1]=1,dp[2]=2
        searched=[1,1,2]
        if n==0:
            return 1
        elif n==1:
            return 1
        elif n==2:
            return 2
        else:
            return self.numWays(n-1)+self.numWays(n-2)

其实仔细看就是Fibonacci数列 那就好办了😀

class Solution:
    def numWays(self, n: int) -> int:
        a,b=1,1
        for i in range(n-1):
            a,b=(a+b)%1000000007,a%1000000007
        return a

第二套代码有些细节的地方在下面这里阐述了比较清楚了，这道题只强调一个动态规划的思想：定义数组含义+递推关系+基准值
https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/solution/mian-shi-ti-10-ii-qing-wa-tiao-tai-jie-wen-ti-dong/

?

?不同路径:(进阶题)

?代码设计思路：

1：定义数组含义：dp[i][j]：代表到第i行j列有dp[i][j]种方法

2：寻找递推关系：类似青蛙跳台阶 由于它只能向下或向右走，故除了第一列和第一行的格子外的任意个格子，都是由上面的格子或者左边的格子跳过来的，因而类比第一题，可得递推关系：dp[i][j]=dp[i-1][j]+dp[i][j-1]

3：初值设定：由2可知，我们需要把dp[i][0](0<=i<=m-1)和dp[0][j]（0<=j-1<=n）定义为1

不妨令全体dp[i][j]为1，因为反正除了第一行或第一列的dp外，都要通过递归关系更新值

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp=[[1]*n for i in range(m)]
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j]=dp[i-1][j]+dp[i][j-1]
        return dp[-1][-1]

蓝桥杯真题分析：数字三角形?（AC）

代码设计分析：

数组定义：dp[i][j]代表第i行j列的最大路径和 由于只能左右移动 (a[i][j]代表i行j列数字)
因此递推关系： dp[i][j]=max(dp[i-1][j]+dp[i-1][j-1])+a[i][j]

初值 第0列第i行只能通过第0列第i-1行左移得到 因此可利用前缀和

? path[i][j]记录左右移动路径，与上一层path有联系，我们定义左-1，右+1

细节补充：原三角形最右那一列的每一个元素 都可以看作由左上角的数字加0得到

因此我们对a[i][j]进行0填充? 代码如下：

n=int(input())
a=[]

for _ in range(n):
    tmp=list(map(int,input().split()))
    tmp+=[0]*(n-len(tmp))
    a.append(tmp)

dp=[[0]*n for i in range(n)]
path=[[0]*n for i in range(n)]#记录左右路径 左-1 右+1

dp[0][0]=a[0][0]
for i in range(1,n):
    dp[i][0]=dp[i-1][0]+a[i][0]#初值
    path[i][0]=path[i-1][0]-1
    

for i in range(1,n):
    for j in range(1,n):
        #dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j]
        if dp[i-1][j]>=dp[i-1][j-1]:#由上一层左拐得到
            dp[i][j]=dp[i-1][j]+a[i][j]
            path[i][j]=path[i-1][j]-1
        else:
            dp[i][j]=dp[i-1][j-1]+a[i][j]
            path[i][j]=path[i-1][j-1]+1

ans=0
for k in range(0,n):
    if abs(path[-1][k])<=1:
        ans=max(ans,dp[-1][k])
print(ans)

?我是小郑 期待与你一起奔赴热爱！冲击蓝桥杯！