public int jumpFloor(int target) {
//方法一:递归方法
//跳一次上一级台阶
//跳两次上2级
//判定特殊条件,返回的是跳法
// if(target ==1 ){
// return 1;
// }
// if(target == 2){
// return 2;
// }
// return jumpFloor(target -1) + jumpFloor(target -2);
//方法二: 尝试记忆化搜索
//寻找重复项,然后用傻缓存
//1.命名一个傻缓存
int [] dp = new int[target+1];
return processus2(target, dp);
}
//记忆化搜索,给一个傻缓存,带着进行递归,用于减少重复项,还是需要栈空间
public static int precessus(int n, int[]dp){
//1.如果之前算过
if(dp[n] != 0){
return dp[n];
}
//2.如果之前没算过
int ans = 0;
if(n ==1 ){
ans = 1;
}else if(n == 2){
ans = 2;
}else{
ans = precessus(n-1, dp) + precessus(n-2, dp);
}
dp[n] = ans;
return ans;
}
//动态规划,不需要栈空间
public static int processus2(int n, int []dp){
for(int i = 1; i < n+1; i++){
if(i == 1){
dp[1] = 1;
}else if(i ==2){
dp[2] = 2;
}else{
dp[i] = dp[i-1]+dp[i-2];
}
}
return dp[n];
}
}