动态规划是什么？

    通俗地讲，动态规划就是将原问题分解为多个相对简单的子问题，并根据子问题的答案求出原问题的解的方法。为了能够明确地拆分子问题，我们需要明确其最优子结构。下图为斐波那契数列的子问题拆分与最优解组合。
                                  

最优子结构

    原问题的最优解由多个子问题的最优解组成，因此我们需要求解每个子问题的最优方案，当然，若子问题中仍可继续拆分，将会递归求解最优方案。
    我们需要描述原问题和子问题的关系，这个关系就是拆分问题并合并最优解的关键，我们通常使用状态转移方程来描述这个关系比如我们常见的斐波那契数列：
                                                                        
其中  是原问题的解，也称为状态。面对不同的条件，状态转移方程也会有所不同，这些条件是需要我们进行编码的判断条件，就上面两条式子来讲，其伪代码就是 
function f(n):
    if n <= 1 return 1;
    else return f(n - 1) + f(n - 2);
我们通过 if-else 语句就可以对状态转移方程进行控制。

举个栗子


    题目来自力扣《300.最长上升子序列》

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例1 

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例2 

输入：nums = [0,1,0,3,2,3]
输出：4

示例3 

输入：nums = [7,7,7,7,7,7,7]
输出：1

    对于这样的题，如果我们考虑使用动态规划去做，那就要思考如何将它的问题进行拆分。面对数组类型的动态规划问题，通常我们有两种思路，下面我们借用示例 1 中的数组进行解释：
  • 每次将问题规模拆分一半，那么第一次拆分就是 [10, 9, 2, 5] 和 [3, 7, 101, 18]，可以看出，这两个子问题的最优解并不能很好地组合成原问题的最优解，因此不考虑这种解题方式。
  • 每次将问题规模减少一个，那么每次拆分后的规模和最优解如下图
                                   
    我们记  为第 n 个数结尾的最长子序列的个数，也就是说，在  问题中第 n 个数一定要在最长子序列里面，而且在最后面，于是我们就可以得出一个结论：

                                         

于是我们又可以从  到  中选一个子序列最长的，进行个数 + 1，赋值给 ，所以我们得出状态转移方程：

                                        

得到了状态转移方程，我们就可以愉快地开始编码啦，以下是 Java 代码实现 
class Solution {
    // 问题：返回最长递增子序列的长度
    public int lengthOfLIS(int[] nums) {
        // dp[i] 意味着以第 i 个元素结尾的最长递增子序列
        int[] dp = new int[nums.length];
        // 因为长度从 1 开始，所以给数组填充 1
        Arrays.fill(dp, 1);
        // 记录所有 f(i) 中最长的长度
        int res = 1;
        for (int i = 1; i < nums.length; ++i) {    // 遍历子问题 f(i)
            for (int j = 0; j < i; ++j) {    // 遍历 1 到 i-1 的子问题，求最长
                if (nums[j] >= nums[i]) continue;
                dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1;
            }
            res = dp[i] > res ? dp[i] : res;
        }
        return res;
    }
}

扩展：动态规划与贪心算法的区别