前言
爬楼梯就是一个斐波那契数列问题,采用动态规划是最合适不过的。
实现原理
初始化:dp[0]=1;dp[1]=2;
转移方程:dp[i]=dp[i-1]+d[i-2];
边界条件:无
具体代码实现
class Solution {
public int climbStairs(int n) {
if(n==1){
return 1;
}
int[] dp=new int[n];
dp[0]=1;
dp[1]=2;
for(int i=2;i<n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n-1];
}
}
QA:内存占用是否可以继续优化?
具体代码实现(通过2个int变量的轮换完成内存的优化)
class Solution {
public int climbStairs(int n) {
if(n==1){
return 1;
}
int a=1;int b=2;
for(int i=2;i<n;i++){
int temp=a+b;
a=b;
b=temp;
}
return b;
}
}
标签:爬楼梯,int,Solution,public,return,Java,数据结构,class,dp
From: https://blog.csdn.net/acuteeagle01/article/details/139538331