【上海校区】月神按2的幂次方来跳台阶

python 未结 0 214
网络营销做什么
网络营销做什么 2021-07-22 15:25
悬赏:12
问题:一共有N个台阶,可以按2的幂次方(1,2,4,8...)来跳,总共有多少种中法

分析:f(0) = 1

第1个台阶,有 f(1-1)种跳法

第2个台阶,有 f(2-1)+f(2-2)种跳法

第3个台阶,有 f(3-1)+f(3-2)种跳法

第4个台阶,有 f(4-1)+f(4-2)+f(4-4)种跳法

第5个台阶,有 f(5-1)+f(5-2)+f(5-4)种跳法

第6个台阶,有 f(6-1)+f(6-2)+f(6-4)种跳法

第7个台阶,有 f(7-1)+f(7-2)+f(7-4)种跳法

第8个台阶,有 f(8-1)+f(8-2)+f(8-4)+f(8-8)种跳法

第9个台阶,有 f(9-1)+f(9-2)+f(9-4)+f(9-8)种跳法

第10个台阶,有 f(10-1)+f(10-2)+f(10-4)+f(10-8)种跳法

.....

推理可得f(n) = f(n-1)+f(n-2*1)+f(n-2*2)+f(n-2*3)+....+f(n-2*MAX),其中是2的MAX次方不超过n时的指数,如n=8时,MAX为3。

故该题可用动态规划来做,保存已经算过的数据,来求新的数。

public class Test {

        public static void main(String[] args) {
                // TODO Auto-generated method stub
                int n = 16;
                int[] dp = new int[n+1];
                dp[0] = 1;
                for(int i=1; i<=n; i++){
                        int idx = fun1(i);
                       
                        //f(n) = f(n-1)+f(n-2*1)+f(n-2*2)+f(n-2*3)+....+f(n-2*MAX)
                        for(int j=0; j<=idx; j++){
                                dp += dp[(int)(i-Math.pow(2, j))];
                        }
                }
                System.out.println(dp[8]);

        }
       
        //求出2的x次方不超过n时的,最大指数(x)
        public static int fun1(int n){
                int idx = 0;
                for(int i=0; i<Integer.MAX_VALUE; i++){
                        if(Math.pow(2, i)>n){
                                idx = i-1;
                                break;
                        }else if(Math.pow(2, i) == n){
                                idx = i;
                                break;
                        }
                }
                return idx;
        }
}

---------------------
作者:另一个我竟然存在
来源:CSDN
原文:https://blog.csdn.net/qq_24034545/article/details/82620735
版权声明:本文为博主原创文章,转载请附上博文链接!

相关标签:
回答
  • 消灭零回复
提交回复