黑马程序员技术交流社区

标题: 【上海校区】月神按2的幂次方来跳台阶 [打印本页]

---

作者: 梦缠绕的时候    时间: 2018-11-26 09:38
标题: 【上海校区】月神按2的幂次方来跳台阶
问题：一共有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
版权声明：本文为博主原创文章，转载请附上博文链接！

---

作者: 不二晨    时间: 2018-11-28 15:46
奈斯

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2