动态规划（Dynamic Programing）
- DP思路
- 题解步骤
- 例题
- 滚动数组初体验（DP问题空间优化）
DP思路
-
看到OJ题需要求最值，就应该形成条件反射——嗯，这题或许要使用贪心算法或者动态规划。当你发现贪心不能解决问题，且原问题规模可缩小时，即可考虑用动态规划求解
-
先把原问题的规模缩成最小的子问题，确定边界
-
逐步扩大子问题，并且通过前面步骤的子问题的解来求最新子问题的解
-
当子问题规模扩大为i时，可推出状态转移方程
例如：原问题dp[i]的解=子问题dp[i-1]的解+子问题dp[i-2]的解
- dp[i]数组的意义：问题变量的状态。随着i的变化dp[i]记录着问题变量状态的变化过程
题解步骤
- 确定原问题与子问题
- 确认状态，dp[i]数组的意义
- 确认边界状态的值
- 确认状态转移方程
（理论晦涩难懂，请看下方例题，长文警告！！！）
例题
动态规划最经典的问题莫过于背包问题了
想要了解的朋友可点击下方的3个传送门
01背包
小破站视频讲解
dalao博客
完全/多重背包
dalao博客
而我更想讲的是下面这题——一道比较简单易懂的dp题
一个机器人位于一个 m x n 网格的左上角，机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
- 网格中的障碍物和空位置分别用 1 和 0 来表示。
- m和n的值均不超过100
来源：力扣（LeetCode）力扣每日一题-20200706
动态规划的题目分为两大类，一种是求最优解类（就是上文所提到的条件反射），典型问题是背包问题，另一种就是计数类，比如这里的统计方案数的问题，它们都存在一定的递推性质。
假设，我们要从左上角的起点a走到右下角的终点b，每次只能向右或者向下移动1格，问：总共有多少条不同路径（暂时不考虑障碍问题）
如下图：
确定原问题：
首先明确：我们的终极目标就是要到b处（从起点走到终点），这就是我们的原问题，这应该很好理解
确定子问题：
- 由图和题目可知，我们要走到方格9(b处)，那么唯有从方格6或者方格8处直接到达（一次只能向下或者向右移动一步）
- 这个时候我们如果先把问题的范围稍微缩小一下，把终极目标改为走到6处
- 同理可得，6可由3或者5直接到达，再次缩小范围，依次类推…3只能由2到达，而2只能由1到达…当我们来到这一步的时候，我们的最小子问题就出来了：有多少路径可由1到达2？（也可以理解为从1到达1才是最小子问题）显而易见只有1条，同理，由1到达4也只有1条路径
逐步扩大子问题：
那么如今我们
- 已知1到2与1到4的路径总和，是不是能求1到5的路径总和了？
- 已知1到2的路径总和，是不是能求1到3的路径总和了？
- 已知1到3和1到5的路径总和，是不是能求1到6的路径总和了？
…
…- 依次类推，我们最终能得到1到6和1到8的路径总和，进而求得我们的终极目标——从a到b处的路径总和
根据我们逐步扩大子问题的过程，我们可以列出下面公式:
cnt[i]：从方格1走到方格i的路径总和
已知1到2与1到4的路径总和，求1到5的路径总和：cnt[5] = cnt[2]+cnt[4];
已知1到2，求1到3的路径总和：cnt[3] = cnt[2];
已知1到3与1到5的路径总和，求1到6的路径总和：cnt[6] = cnt[3]+cnt[5];
…
…
已知1到6与1到8的路径总和，求1到9的路径总和：cnt[9] = cnt[6]+cnt[8];
dp[i]的意义：
cnt[i]：从方格1走到方格i的路径总和
此处的 cnt[i] 即我们前文所提到的 dp[i]
从方格1走到方格i的路径总和 即为 dp[i]的意义
我们再把上述公式化为二维进行表示，即：
cnt[1][1] = cnt[0][1]+cnt[1][0];
cnt[0][2] = cnt[0][1];
cnt[1][2] = cnt[1][1]+cnt[0][2];
…
…
cnt[2][2] = cnt[1][2]+cnt[2][1];
到了这一步，我们可以发现一个规律：
cnt[ i ] [ j ] = cnt[ i - 1] [ j ] + cnt[ i ] [ j - 1];
这就是我们前文所提到的状态转移方程 ，其实所谓的状态转移方程是可以理解为题目所遵循的一个规律，就像一个二元一次方程y=2x+1一样，结果y是随着参数x的变化而变化的，而我们这里的cnt[ i - 1] [ j ] 和cnt[ i ] [ j - 1 ] 也影响着cnt[ i ] [ j ]
依据状态转移方程，从起点（i=0,j=0）出发，慢慢地往下递推，即可求出到达其他所有点的路径总和
至于障碍什么的，加个if就啦
代码如下：（要仔细看注释哦，注释的颜色有点浅emm…）
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
//初始化dp数组，此处dp数组即为上文提到的cnt数组
int dp[100][100] = {0};
if(!obstacleGrid.size()) return 0;
int m = obstacleGrid.size(),n = obstacleGrid[0].size();
//核心代码：双重for循环遍历原地图
for(int i = 0;i < m;i++){
for(int j = 0;j < n;j++){
//up:从起点到obstacleGrid[i][j]的上面方格的路径和
//left:从起点到obstacleGrid[i][j]的左边方格的路径和
//obstacleGrid[i][j] = up + left
int up = 0,left = 0;
//判断越界！！！
if(i-1>=0 && obstacleGrid[i-1][j]!=1) up = dp[i-1][j];
if(j-1>=0 && obstacleGrid[i][j-1]!=1) left = dp[i][j-1];
//判断障碍
if(obstacleGrid[i][j]!=1)
if(i==0 && j==0) dp[i][j] = 1;
else dp[i][j] = up+left;
}
}
//理解了此题dp数组的意义，返回值自然就是小case了
return dp[m-1][n-1];
}
};
看到这里，如果你对这题已经大概理解，也对dp已经有了些许的感觉，就可以继续看下方的官方题解（解题思路基本一样）
官方题解：
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int n = obstacleGrid.size(), m = obstacleGrid.at(0).size();
vector <int> f(m);
f[0] = (obstacleGrid[0][0] == 0);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (obstacleGrid[i][j] == 1) {
f[j] = 0;
continue;
}
if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
f[j] += f[j - 1];
}
}
}
return f.back();
}
};
//作者：LeetCode-Solution
//链接：https://leetcode-cn.com/problems/unique-paths-ii/solution/bu-tong-lu-jing-ii-by-leetcode-solution-2/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
咦？好像有点不对？ 如果细心看完这2个题解代码的朋友，就会发现：
菜鸡的代码：空间复杂度O(mn)
官方的代码：空间复杂度O(m)
这就是接下来要提到的DP问题空间复杂度优化了
（建议先理解了这题的dp思想，再去理解滚动数组）
滚动数组初体验（DP问题空间优化）
滚动数组，通俗来说，就是让数组滚动起来，用更小的空间去存储数据。
看回咱们这题，我们的状态转移方程：
cnt[ i ] [ j ] = cnt[ i - 1] [ j ] + cnt[ i ] [ j - 1];
可以看出cnt[ i ] [ j ]只与cnt[ i - 1] [ j ]和cnt[ i ] [ j -1]这两个数有关，那么如果我们开辟出m*n的空间去把所有的cnt的值都存起来，是不是显得有点浪费呢？
在一维的滚动数组中，我们把cnt[ i ] [ j ] 的内容放到了cnt[ i ] 中，此时cnt[ i ]的意义就是当前行（第j行）的第i个元素的值，因为在我们的两份代码中，都是一个双重for循环，一行一行地对map进行迭代，而我们的cnt[ i ] 数组就随着我们的迭代进行滚动，代表着当前行第i个元素的值
cnt[ i ] [ j ] 是等于 cnt[ i -1] [ j ] 加上 cnt[ i ] [ j -1] 的，而转换到一维数组中：cnt[ i ] 就是等于 cnt[ i - 1] 加上 cnt[ i ]
对，没错，就是加上他自己本身原来所存储的值
因为当你要计算cnt[ i ] [ j ] 的值时，cnt[ i ] 存储的其实还是上一行cnt[ i ] 的值，即cnt[ i ] [ j - 1 ] 的值
（请结合下图理解）
