动态规划

动态规划算法同分治算法类似。其基本思想是将待求解的问题分解为若干个子问题，先求解子问题，然后从这些子问题的解中得到原问题的解。与递归分治不同的点在于，动态规划使用一张表来记录所有已解决子问题的答案。不管该子问题以后是否被用到，只要它计算过，就将结果填入表中。这就是动态规划的基本思想。

通常可以按照以下步骤设计动态规划算法：

1. 找出最优解的性质，并刻画其结构特征。
2. 递归地定义最优值。
3. 以自底向上的方式计算出最优值。
4. 根据计算最优值时得到的信息，构造出最优解。

典型的算法案例就是计算斐波那契函数：

斐波那契数学公式

1. 递归实现: 自顶向下求解，然后逐步返回求解结果

public static long fibonacci(int n){
    if ( n <= 0){
        return 0;
    }
    if (n == 1){
        return 1;
    }else if (n == 2){
        return 2;
    }

    return fibonacci(n-1) + fibonacci(n - 2);
}

2. 使用动态规划循环实现：自底向上，逐步计算出f(n)

 public static long f(int n) {
     
     int[] result = {0, 1, 2};
     if (n < 0) {
         return 0;
     }

     if (n < 3) {
         return result[n];
     }

    /**
     * firstNum = f(n - 1)
     * lastNum = f(n - 2)
     */
     int lastNum = result[1];
     int firstNum = result[2];
     int num = 0;
     for (int i = 3; i <= n; i++) {
         num = firstNum + lastNum;
         lastNum = firstNum;
         firstNum = num;
     }
     return num;
}