动态规划（Dynamic programming，简称DP）

动态规划算法的基本思想与分治法类似，也是将求解的问题分解为若干字问题，按顺序求解子阶段，前一子问题的解，为后一子问题提供了有用的信息。在求解任意子问题，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解决。

适用情况

最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构性质（即满足最优原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
无后效性。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的最大的问题的求解决策影响。
子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题。有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算依据计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

求解的基本步骤

分析最优解的性质，并刻画其结构特征。
递归的定义最优解。
以自底向上或自顶向下的记忆方式（备忘录）计算出最优值。
根据计算最优值时得到的信息，构造问题的最优解。

算法实现

动态规划的主要难点在于理论上的设计，也即是上面4个步骤的确定，一旦设计完成，实现部分就会非常简单。使用动态规划求解问题，最重要的就是确定动态规划三要素：

问题阶段
每个阶段的状态
从前一个阶段转化到后一个阶段之间的速推关系

斐波那契数列

70.爬楼梯

定义一个数组 dp 存储上楼梯的方法数（为了方便讨论，数组下标从 1 开始），dp[i] 表示走到第 i 个楼梯的方法数目。
第 i 个楼梯可以从第 i-1 和 i-2 个楼梯再走一步到达，走到第 i 个楼梯的方法数为走到第 i-1 和第 i-2 个楼梯的方法数之和。

198.Hourse Robber

定义 dp 数组用来存储最大的抢劫量，其中 dp[i] 表示抢到第 i 个住户时的最大抢劫量。
由于不能抢劫邻近住户，如果抢劫了第 i -1 个住户，那么就不能再抢劫第 i 个住户。dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])

213.强盗在环形街区抢劫

偷了0以后，第n-1间房子不能偷。
分情况，偷不偷第1栋房，偷就算1到n - 1栋的最大值，不偷就算2到n栋的最大值，求这两个的最大值即可

矩阵路径

矩阵的最小路径和

64. Minimum Path Sum (Medium)
运用动态规划，我们在递归的时候了解到，（i,j）位置的值依赖它左边或者上边的值，所以我们就先把它依赖的求出来，然后从左上开始向（i,j）求，相当于把递归的过程反过来。申请一个新的二维数组空间，分别求出第一行和第一列的累计和的值，然后再求（i,j）位置的值时就可以根据已经求出的第一行和第一列的累计和来算（把每个i,j位置的路径和都算出来），先找出不被依赖的，再求出依赖的。

步骤：
假设矩阵m的大小为M×N，行数为M，列数为N。

dp[i][j]：
生成大小和m一样的矩阵dp，dp[i][j]的值表示从左上角（即(0，0)）位置走到(i ，j)位置的最小路径和。

含义是比较从(0，0)位置开始，经过(i-1，j)位置最终到达(i，j)的最小路径和经过(i ，j-1)位置最终到达(i ，j)的最小路径之间，哪条路径的路径和更小。
更小的路径和就是dp[i][j]的值。

矩阵的总路径数

62. Unique Paths (Medium)

数组区间

数据区间和

303. Range Sum Query - Immutable (Easy)

求区间 i ~ j 的和，可以转换为 sum[j + 1] - sum[i]，其中 sum[i] 为 0 ~ i - 1 的和。

数组中等差递增子区间的个数

413. Arithmetic Slices (Medium)