动态规划

什么是动态规划？

动态规划算法常用来请求最优值问题，并且这类问题具有公共子问题的特征，即一个大问题的值可以先计算子问题的值，然后父问题的值可以从子问题的值计算得到，以此类推，最终得到大问题的值。

动态规划的解题步骤

这里以斐波那契数列 为例子，讲解动态规划的解题步骤。斐波那契数列问题，一般会给你一段初始数列，如1、1、2、3、5、8、13、21、34…，然后让你求解第n个数是多少。

分析问题，得到状态转移方程

这里我看可以看到，当n>=3时，fn=fn-1+fn-2。也就是说一个大问题的值可以拆分成俩个小问题的值相加，而一个小问题的拆分又满足上面这个特征，因此满足动态规划的定义。

找出公共子问题，得到它们的值且记录到备忘录

从初始数列可以看到，对于n>=3时，它们都有着公共子问题，也就是初始数列1,1。对于这个问题，备忘录可以使用一个一维数组来记录初始数列。这里补充一点，如果用递归来实现的话，对于公共子问题的值会重复进行计算。

具体实现

public static void main(String[] args){
        int n = 5;
        int dp[] = new int [n+1];
        dp[1]=1;
        dp[2]=1;
        for(int i=3;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        System.out.println(dp[n]);
    }

题目实战

1. 牛客网-斐波那契数列