什么是动态规划
https://www.zhihu.com/question/410196236/answer/2317284424
用一句话解释动态规划就是 “记住你之前做过的事”，如果更准确些，其实是 “记住你之前得到的答案”。
我举个大家工作中经常遇到的例子。
在软件开发中，大家经常会遇到一些系统配置的问题，配置不对，系统就会报错，这个时候一般都会去 Google 或者是查阅相关的文档，花了一定的时间将配置修改好。
过了一段时间，去到另一个系统，遇到类似的问题，这个时候已经记不清之前修改过的配置文件长什么样，这个时候有两种方案，一种方案还是去 Google 或者查阅文档，另一种方案是借鉴之前修改过的配置，第一种做法其实是万金油，因为你遇到的任何问题其实都可以去 Google，去查阅相关文件找答案，但是这会花费一定的时间，相比之下，第二种方案肯定会更加地节约时间，但是这个方案是有条件的，条件如下：
之前的问题和当前的问题有着关联性，换句话说，之前问题得到的答案可以帮助解决当前问题
需要记录之前问题的答案
当然在这个例子中，可以看到的是，上面这两个条件均满足，大可去到之前配置过的文件中，将配置拷贝过来，然后做些细微的调整即可解决当前问题，节约了大量的时间。
不知道你是否从这些描述中发现，对于一个动态规划问题，我们只需要从两个方面考虑，那就是 找出问题之间的联系，以及 记录答案，这里的难点其实是找出问题之间的联系，记录答案只是顺带的事情，利用一些简单的数据结构就可以做到。
思考动态规划问题的四个步骤
一般解决动态规划问题，分为四个步骤，分别是
问题拆解，找到问题之间的具体联系
状态定义
递推方程推导
实现
这里面的重点其实是前两个，如果前两个步骤顺利完成，后面的递推方程推导和代码实现会变得非常简单。
1 动态规划要素
动态规划有三要素：阶段、状态和决策。
阶段：
把一个问题的过程，恰当地分为若干个相互联系的阶段，以便于按一定的次序去求解。描述阶段的变量称为阶段变量。阶段的划分，一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。
状态：
表示每个阶段开始所处的自然状况或客观条件。通常一个阶段有若干个状态（也可能只有一个状态），描述过程状态的变量称为状态变量。
决策：
表示当过程处于某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状态，这种决定称为决策。
一般流程：
划分阶段 -> 正确选择状态变量 -> 确定状态转移方程
-> 确定阶段指标函数和最优指标函数，建立动态规划基本方程。
2 动态规划的适用范围
动态规划用于解决多阶段决策最优化问题，但也不是所有最优化问题都可以用动态规划来解答。用动态规划的最优化问题要满足两个条件：
a) 最优子结构(最优化原理)
作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决策所形成的状态而言，余下的决策序列必然构成最优子策略。”也就是说，一个最优策略的子策略也是最优的。
b) 无后效性
如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响。就是说在状态i求解时用到状态j，状态j求解用到状态k...,状态N。而状态N要用到状态i，这样的求解过程形成了环就没法用动态规划解答。也就是说当前状态是前面状态的完美总结，现在与过去无关。有的问题换一个划分状态或阶段的方法就满足无后效性，这样的问题仍然可以用动态规划解。
如果状态变量不能满足无后效性的要求，应适当地改变状态的定义或规定方法。
3 动态规划解决问题的一般思路
拿到多阶段决策最优化问题后，第一步要判断这个问题是否可以用动态规划解决，如果不能就要考虑搜索或者贪心了。当确定问题可以用动态规划后，可以用下面介绍的方法解决问题：
a) 模型匹配法
这个是最先考虑的。主要是看看问题是不是自己熟悉的某个基本的模型，如背包模型等，是的话就直接套用了，当然要注意其中的变动。有很多考题是基本模型的变型，小心条件。这些基本的模型将在下面的分类中以算法题的形式一一介绍。
b) 三要素法
仔细分析问题尝试着确定动态规划的三要素，不同的问题的确定方形不同：
先确定阶段的问题：数塔问题和走路问题。
先确定状态的问题：大多数都是先确定状态。
先确定决策问题：背包问题。
一般都是先从比较明显的地方入手，至于怎么知道哪个明显就看经验，多做题就会发现。
c) 寻找规律法
耐心分析几组数据，找找有没有什么规律。
d) 边界条件法
找到问题的边界条件，然后考虑边界条件与它邻接状态之间的关系。
题目实战
但凡涉及到动态规划的题目都离不开一道例题：爬楼梯。
题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入：2
输出：2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入：3
输出：3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
题目解析
爬楼梯，可以爬一步也可以爬两步，问有多少种不同的方式到达终点，我们按照上面提到的四个步骤进行分析：
问题拆解：
我们到达第 n 个楼梯可以从第 n - 1 个楼梯和第 n - 2 个楼梯到达，因此第 n 个问题可以拆解成第 n - 1 个问题和第 n - 2 个问题，第 n - 1 个问题和第 n - 2 个问题又可以继续往下拆，直到第 0 个问题，也就是第 0 个楼梯 (起点)
状态定义
“问题拆解” 中已经提到了，第 n 个楼梯会和第 n - 1 和第 n - 2 个楼梯有关联，那么具体的联系是什么呢？你可以这样思考，第 n - 1 个问题里面的答案其实是从起点到达第 n - 1 个楼梯的路径总数，n - 2 同理，从第 n - 1 个楼梯可以到达第 n 个楼梯，从第 n - 2 也可以，并且路径没有重复，因此我们可以把第 i 个状态定义为 “从起点到达第 i 个楼梯的路径总数”，状态之间的联系其实是相加的关系。
递推方程
“状态定义” 中我们已经定义好了状态，也知道第 i 个状态可以由第 i - 1 个状态和第 i - 2 个状态通过相加得到，因此递推方程就出来了
dp[i] = dp[i - 1] + dp[i - 2]实现
你其实可以从递推方程看到，我们需要有一个初始值来方便我们计算，起始位置不需要移动
dp[0] = 0，第 1 层楼梯只能从起始位置到达，因此dp[1] = 1，第 2 层楼梯可以从起始位置和第 1 层楼梯到达，因此dp[2] = 2，有了这些初始值，后面就可以通过这几个初始值进行递推得到。
参考代码
public int climbStairs(int n) {
if (n == 1) {
return 1;
}
int[] dp = new int[n + 1]; // 多开一位，考虑起始位置
dp[0] = 0; dp[1] = 1; dp[2] = 2;
for (int i = 3; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}实验要求：请使用MATLAB编程实现n=20的爬楼梯问题的解，并输出所有解。
==================================
如何学好动态规划
链接：https://www.zhihu.com/question/291280715/answer/1916669734
大家都知道算法里的桂冠是动态规划，无论是学习还是面试，动态规划都是最重要的。
其实去网上搜一搜也可以发现，能把动态规划讲清楚的资料挺少的，因为动规确实很难！要给别人讲清楚更难！
《剑指offer》上 动规的题目很少，经典的算法书籍《算法4》 没有讲 动规，而《算法导论》讲的动规基本属于劝退级别的。
那么如何学好动态规划呢？
我来按照如下四点，来回答这个问题
动态规划的解题步骤
动态规划应该如何debug
关于动态规划的疑惑
如何刷题动态规划
动态规划的解题步骤
做动规题目的时候，很多同学会陷入一个误区，就是以为把状态转移公式背下来，照葫芦画瓢改改，就开始写代码，甚至把题目AC之后，都不太清楚dp[i]表示的是什么。
这就是一种朦胧的状态，然后就把题给过了，遇到稍稍难一点的，可能直接就不会了，然后看题解，然后继续照葫芦画瓢陷入这种恶性循环中。
状态转移公式（递推公式）是很重要，但动规不仅仅只有递推公式。
对于动态规划问题，我将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！
确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组
一些同学可能想为什么要先确定递推公式，然后在考虑初始化呢？
因为一些情况是递推公式决定了dp数组要如何初始化！
后面的讲解中我都是围绕着这五点来进行讲解。
可能刷过动态规划题目的同学可能都知道递推公式的重要性，感觉确定了递推公式这道题目就解出来了。
其实 确定递推公式 仅仅是解题里的一步而已！
一些同学知道递推公式，但搞不清楚dp数组应该如何初始化，或者正确的遍历顺序，以至于记下来公式，但写的程序怎么改都通过不了。
后序的讲解的大家就会慢慢感受到这五步的重要性了。
动态规划应该如何debug
相信动规的题目，很大部分同学都是这样做的。
看一下题解，感觉看懂了，然后照葫芦画瓢，如果能正好画对了，万事大吉，一旦要是没通过，就怎么改都通过不了，对 dp数组的初始化，递归公式，遍历顺序，处于一种黑盒的理解状态。
写动规题目，代码出问题很正常！
找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的！
一些同学对于dp的学习是黑盒的状态，就是不清楚dp数组的含义，不懂为什么这么初始化，递推公式背下来了，遍历顺序靠习惯就是这么写的，然后一鼓作气写出代码，如果代码能通过万事大吉，通过不了的话就凭感觉改一改。
这是一个很不好的习惯！
做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。
然后再写代码，如果代码没通过就打印dp数组，看看是不是和自己预先推导的哪里不一样。
如果打印出来和自己预先模拟推导是一样的，那么就是自己的递归公式、初始化或者遍历顺序有问题了。
如果和自己预先模拟推导的不一样，那么就是代码实现细节有问题。
这样才是一个完整的思考过程，而不是一旦代码出问题，就毫无头绪的东改改西改改，最后过不了，或者说是稀里糊涂的过了。
这也是我为什么在动规五步曲里强调推导dp数组的重要性。
举个例子：在「代码随想录」刷题小分队微信群里，一些同学可能代码通过不了，会把代码抛到讨论群里问：我这里代码都已经和题解一模一样了，为什么通过不了呢？
发出这样的问题之前，其实可以自己先思考这三个问题：
这道题目我举例推导状态转移公式了么？
我打印dp数组的日志了么？
打印出来了dp数组和我想的一样么？
如果这灵魂三问自己都做到了，基本上这道题目也就解决了，或者更清晰的知道自己究竟是哪一点不明白，是状态转移不明白，还是实现代码不知道该怎么写，还是不理解遍历dp数组的顺序。
关于动态规划的疑惑
还有不少同学对动规的理解是：递推公式是才是最难最重要的，只要想出递归公式，其他都好办。
其实这么想的同学基本对动规理解的不到位的。
动规五部曲里，哪一部没想清楚，这道题目基本就做不出来，即使做出来了也没有想清楚，而是朦朦胧胧的就把题目过了。
如果想不清楚dp数组的具体含义，递归公式从何谈起，甚至初始化的时候就写错了。
例如动态规划：不同路径还不够，要有障碍！ 在这道题目中，初始化才是重头戏
如果看过背包系列，特别是完全背包，那么两层for循环先后顺序绝对可以搞懵很多人，反而递归公式是简单的。
至于推导dp数组的重要性，动规专题里几乎每篇Carl都反复强调，当程序结果不对的时候，一定要自己推导公式，看看和程序打印的日志是否一样。
如何刷题动态规划
先来一份 动态规划刷题大纲：
关于动态规划，在专题第一篇关于动态规划，你该了解这些！就说了动规五部曲，而且强调了五部对解动规题目至关重要！
这是Carl做过一百多道动规题目总结出来的经验结晶啊，如果大家跟着「代码随想哦」刷过动规专题，一定会对这动规五部曲的作用感受极其深刻。
动规五部曲分别为：
确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组
动规专题刚开始的时候，讲的题目比较简单，不少同学和我反应：这么简单的题目 讲的复杂了，不用那么多步骤分析，想出递推公式直接就AC这道题目了。
Carl的观点一直都是 简单题是用来 巩固方法论的。 简单题目是可以靠感觉，但后面稍稍难一点的题目，估计感觉就不好使了。
在动规专题讲解中，也充分体现出，这动规五部曲的重要性。
动规刷题详细路线：
动划基础
背包问题系列
打家劫舍系列
股票系列
子序列系列
同时我将刷题攻略整理在Github上，瞬间登上了 Github全球热榜，
https://github.com/youngyangyang04/leetcode-master
github 项目截图：
这个项目里面有200道经典算法题目刷题顺序、配有60w字的详细图解，常用算法模板总结，以及难点视频讲解，按照list一道一道刷就可以了！
去看看吧，这个Github算法学习项目会惊艳到你！
youngyangyang04/leetcode-master
可以在B站上关注我，上面有很多算法的讲解视频。
同时也整理出一份PDF，pdf中不仅有刷题大纲、刷题顺序，还有详细图解，每一本pdf发布之后都广受好评先，PDF中攻击20w字详细图解了 100多道力扣上的经典题目，上图：
无论现在要不要学习算法，先去下载吧，你会发现详见很晚！
62.不同路径
题目链接：https://leetcode-cn.com/problems/unique-paths/
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
向右 -> 向右 -> 向下 向右 -> 向下 -> 向右 向下 -> 向右 -> 向右
示例 3：
输入：m = 7, n = 3
输出：28
示例 4：
输入：m = 3, n = 3
输出：6
提示：
1 <= m, n <= 100 题目数据保证答案小于等于 2 * 10^9
思路
深搜
这道题目，刚一看最直观的想法就是用图论里的深搜，来枚举出来有多少种路径。
注意题目中说机器人每次只能向下或者向右移动一步，那么其实机器人走过的路径可以抽象为一颗二叉树，而叶子节点就是终点！
如图举例：
此时问题就可以转化为求二叉树叶子节点的个数，代码如下：
class Solution {
private:
int dfs(int i, int j, int m, int n) {
if (i > m || j > n) return 0; // 越界了
if (i == m && j == n) return 1; // 找到一种方法，相当于找到了叶子节点
return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);
}
public:
int uniquePaths(int m, int n) {
return dfs(1, 1, m, n);
}
};
大家如果提交了代码就会发现超时了！
来分析一下时间复杂度，这个深搜的算法，其实就是要遍历整个二叉树。
这颗树的深度其实就是m+n-1（深度按从1开始计算）。
那二叉树的节点个数就是 2^(m + n - 1) - 1。可以理解深搜的算法就是遍历了整个满二叉树（其实没有遍历整个满二叉树，只是近似而已）
所以上面深搜代码的时间复杂度为O(2^(m + n - 1) - 1)，可以看出，这是指数级别的时间复杂度，是非常大的。
动态规划
机器人从(0 , 0) 位置出发，到(m - 1, n - 1)终点。
按照动规五部曲来分析：
确定dp数组（dp table）以及下标的含义
dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
确定递推公式
想要求dp[i][j]，只能有两个方向来推导出来，即dp[i - 1][j] 和 dp[i][j - 1]。
此时在回顾一下 dp[i - 1][j] 表示啥，是从(0, 0)的位置到(i - 1, j)有几条路径，dp[i][j - 1]同理。
那么很自然，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为dp[i][j]只有这两个方向过来。
dp数组的初始化
如何初始化呢，首先dp[i][0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp[0][j]也同理。
所以初始化代码为：
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
确定遍历顺序
这里要看一下递归公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。
这样就可以保证推导dp[i][j]的时候，dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的。
举例推导dp数组
如图所示：
以上动规五部曲分析完毕，C++代码如下：
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m, vector<int>(n, 0));
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
};
时间复杂度：O(m * n) 空间复杂度：O(m * n)
其实用一个一维数组（也可以理解是滚动数组）就可以了，但是不利于理解，可以优化点空间，建议先理解了二维，在理解一维，C++代码如下：
class Solution {
public:
int uniquePaths(int m, int n) {
vector<int> dp(n);
for (int i = 0; i < n; i++) dp[i] = 1;
for (int j = 1; j < m; j++) {
for (int i = 1; i < n; i++) {
dp[i] += dp[i - 1];
}
}
return dp[n - 1];
}
};
时间复杂度：O(m * n) 空间复杂度：O(n)
动态规划：不同路径还不够，要有障碍！
https://mp.weixin.qq.com/s/lhqF0O4le9-wvalptOVOww
