距离蓝桥杯64天 快和小郑一起准备蓝桥杯吧
蓝桥杯真题题目链接：数字三角形
Leedcode青蛙跳台阶
Leedcode不同路径
特此鸣谢这位作者的点播，小郑从中获益不少
青蛙跳台阶：(入门题)
思路简单:解析见代码（虽然递归超时，思想值得学习）
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
第二套代码有些细节的地方在下面这里阐述了比较清楚了，这道题只强调一个动态规划的思想：定义数组含义+递推关系+基准值
不同路径:(进阶题)
代码设计思路：
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)
我是小郑 期待与你一起奔赴热爱！冲击蓝桥杯！
