题解 | #跳台阶扩展问题#

跳台阶扩展问题

http://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387

刚开始用记忆化动态规划来做,比较简单,但是没有发现它的规律。

过完测试用例发现,我们求的f[n] = f[n-1]+f[n-2]+f[n-3]+... +f[0]

而f[n-1]=f[n-2]+f[n-3]+...+f[0]

所以f[n]正好等于2*f[n-1]

已知f[0] = f[1] = 1

所以容易得到f[2]=2,f[3]=4,f[4]=8 由此得到规律-->f[n]=2*(n-1)【n>=1】

public class Solution {

public int jumpFloorII(int target) {
    
    //方法一 记忆动态规划
    if(target<=1)
        return 1;
    int[] dp = new int[50];
    for(int i=1;i<50;++i){
        dp[i] = 1;
    }
    for(int i=2;i<=target;++i){
        int index=1;
        while(i-index>=0){
            dp[i] += dp[i-index];
            index++;
        }
    }
    return dp[target];
    
    //方法二 找规律
    return (int)Math.pow(2,target-1);
}

}

阿勇算法解集 文章被收录于专栏

对一些基础的,经典的题目的算法题解,每道题的题解尽量做到一题多解,举一反三。其中每一个题解中,若是参考了其他牛人的想法,我会备注出来。

全部评论

相关推荐

昨天 13:16
湖南工学院 Java
点赞 评论 收藏
分享
昨天 10:56
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务