当前位置：网站首页>剑指Offer 71：跳台阶扩展问题

剑指Offer 71：跳台阶扩展问题

2022-07-19 19:58:00 【斯沃福德】

链接
题目：
在这里插入图片描述

思路：动态规划

逆向思维，在n阶台阶上往下走，共有1+2+…n种方法；
所以f(n) = f(n−1)+f(n−2)+…+f(n−(n−1))+f(n−n) => f(0)+f(1)+f(2)+…+f(n−1)
因为f(n−1)=f(n−2)+f(n−3)+…+f((n−1)−(n−2))+f((n−1)−(n−1))；
经整理得f(n) = f(n−1)+f(n−1) = 2∗f(n−1) ，因此每级台阶方案数是前面一级台阶方案数的2倍。

import java.util.*;
public class Solution {
    
    int[] memo;
    public int jumpFloorII(int n) {
    
        memo=new int[n+1];
        Arrays.fill(memo,-1);
        return dp(n);
    }
    //
    int dp(int n){
    
        //base case
        if(n<=2){
    
            return n;
        }
        //重叠子问题
        if(memo[n]!=-1){
    
            return memo[n];
        }
        memo[n]=dp(n-1) * 2;
        return memo[n];
    }
}
原网站

版权声明
本文为[斯沃福德]所创，转载请带上原文链接，感谢
https://blog.csdn.net/Swofford/article/details/125875945

边栏推荐

猜你喜欢

随机推荐