动态规划/斐波那契数列

动态规划

存储结构：存储运行过程中的结果

• 动态规划数组

3个使用前提：

1. 最优性原理：求解子问题等价于求解大问题
2. 无后效性：后面的操作不会影响前面的结果
3. 重叠子问题：非必要条件，使用递归求解斐波那契数列时，由于存在重叠子问题造成重复计算

使用递归求解斐波那契数列时，由于存在重叠子问题造成重复计算

• 重叠子问题，第3个项的解=前两项之和，
• 递归解决，造成重复计算
• 动态规划解决，由于使用了动态规划数组，存储了运算过程中的解，不会有重复计算

斐波那契

• Fibonacci数列
• f(0)=0
• f(1)=1
• f(n)=f(n-1+f(n-2)

代码

package xcrj.kchalgorithm.dynamicPrograming;

/** * Fibonacci数列 * f(0)=0 * f(1)=1 * f(n)=f(n-1+f(n-2) * <p> * 动态规划法 * 运行过程存储结构：动态规划数组 * <p> * 3个前提： * 1. 最优性原理：对子问题的求解等价于对大问题的求解 * 2. 无后效性：后面的操作不会影响前项的值 * 3. 存在重叠子问题（非必要条件）：前2个数之和是第3个数的值 * <p> * 解法： * 1. 顺序解法：fibonacci是顺序解法 * 2. 逆序解法 */
public class Fibonacci {
    
    // 存储结构 动态规划数组
    private static int[] dynamicPrograming;
    // 累计运行次数
    private static int count = 1;

    /** * 动态规划求解斐波那契数列 * * @param n 数列的第n个数 */
    public static void fibonacci(int n) {
    
        dynamicPrograming = new int[n];
        dynamicPrograming[0] = 1;
        dynamicPrograming[1] = 1;
        for (int i = 2; i < n; i++) {
    
            dynamicPrograming[i] = dynamicPrograming[i - 1] + dynamicPrograming[i - 2];
        }
        System.out.println(dynamicPrograming[n - 1]);
    }

    public static void main(String[] args) {
    
        fibonacci(6);
    }
}