动态规划

需求：有10步台阶，每次只能走一级阶梯，或者走两级阶梯，总共有多少种走法？

比如每次走一级阶梯，那么需要走10步，一种走法；每次走两级阶梯，那么需要走5步，第二种走法。

动态规划包括：最优子结构、边界、状态转移（重复方法体）；

要到第10级台阶，那么只有两种走法，9+8，那么它们就是“最优子结构”；

到了最后，一步，或者2步，就不用再优化，这就是“边界”，如果没有边界，那么问题就无边无际，得不到实际答案；

要到第9级台阶，那么只有两种走法，7+8，以此类推，这就是状态转移（我个人理解为重复方法体）；

具体代码如下：

package com.atguigu.dynamicplanning;

/**
 * 动态规划，需求：共10级台阶，每次只能跨1级，或者跨2级，求多少中走法
 * 
 * @author Administrator 解题思路，要达到10级阶梯，只有两种走法，8步，和9步，这是--最优子结构，
 *         那么解决第8步呢，又要看6和7步， 当只有1级台阶或者2级的时候，就可以得出结果，不需要继续简化（计算）。这就是--边界。 f(n) =
 *         f(n-1)+ f(n-2) 就是阶段与阶段之间的--"状态转移方程"
 * 
 *         递归算法：虽然能计算结果，但是时间复杂度太高，运算过的结果还会继续运算，会形成二叉树， 时间复杂度就可以看做 0(2^n)。
 * 
 *         备忘录算法： 运用HashMap当做备忘录，因为不可重复，每次计算f(n)都会去map中匹配元素
 *         如果map中存在则返回结果，不存在就存入。 解决了时间复杂度。但还可以继续优化。
 * 
 *         思路逆转：自底向上运算，用迭代的方式推导出结果。f(3)=f(1)+f(2), f(4)=f(3)+f(2) 引入一个temp变量
 *         ，代表当前迭代的结果值，实现了时间和空间上的最优化
 * 
 */
public class GetWays {

    static int n = 10;

    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        
        GetWays dp = new GetWays();
        int b = dp.getWay(n);
        System.out.println(b);
        
        long endTime = System.currentTimeMillis();
        System.out.println("程序运行时间：" + (endTime - startTime) + "ms");
    }

    public int getWay(int n) {

        if (n < 1) { // 自底而上的推导，f(3)=f(1)+f(2), f(4)=f(3)+f(2),
                        // 思维逆转，时间空间复杂度进一步优化
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int a = 1;
        int b = 2;
        int temp = 0; // 步数，f(3)=f(1)+f(2) 相当于f(3)
        for (int i = 3; i < n; i++) { // n 的值就是边界
            temp = a + b; 
            a = b; // 然后把b的值赋给a
            b = temp; // 再把步数的值赋给b 进行重新计算

        }

        return temp;

        // if(n<1){ 利用备忘录，HASHMAP表来存放已经计算过的走法，时间复杂度进行优化
        // return 0;
        // }if (n==1) {
        // return 1;
        // }if (n==2) {
        // return 2;
        // }
        // if (map.contains(n)) {
        // return map.get(n);
        // }else {
        // int value = getWay(n-1, map)+ getWay(n-2, map);
        // map.put(n, value);
        // return value;
        // }

        // 递归的解法 要计算f(n) 就要计算f(n-1)+f(n-2)，会生成一个二叉树，时间复杂度太高，计算次数太多
        // if(n<1){
        // return 0;
        // }if (n==1) {
        // return 1;
        // }if (n==2) {
        // return 2;
        // }
        //
        // return getWay(n-1) + getWay(n-2);
        //

    }
}