这篇文章记述了关于动态规划的知识点。
每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划。
每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到
这个性质叫做最优子结构；
而不管之前这个状态是如何得到的
这个性质叫做无后效性。
编辑距离
这次给的这道题比上面的难一些，在 leetcdoe 的定位是 hard 级别。好像是 leetcode 的第 72 号题。
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符 删除一个字符 替换一个字符
1 | 示例： |
还是老样子，按照上面三个步骤来，并且我这里可以告诉你，90% 的字符串问题都可以用动态规划解决，并且90%是采用二维数组。
步骤一、定义数组元素的含义
由于我们的目的求将 word1 转换成 word2 所使用的最少操作数 。那我们就定义 dp[i] [j]的含义为：**当字符串 word1 的长度为 i，字符串 word2 的长度为 j 时，将 word1 转化为 word2 所使用的最少操作次数为 dp[i] [j]**。
作者：帅地
链接：https://www.zhihu.com/question/23995189/answer/1094101149
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
步骤二：找出关系数组元素间的关系式
接下来我们就要找 dp[i] [j] 元素之间的关系了，比起其他题，这道题相对比较难找一点，但是，不管多难找，大部分情况下，dp[i] [j] 和 dp[i-1] [j]、dp[i] [j-1]、dp[i-1] [j-1] 肯定存在某种关系。因为我们的目标就是，**从规模小的，通过一些操作，推导出规模大的。对于这道题，我们可以对 word1 进行三种操作
插入一个字符 删除一个字符 替换一个字符
由于我们是要让操作的次数最小，所以我们要寻找最佳操作。那么有如下关系式：
一、如果我们 word1[i] 与 word2 [j] 相等，这个时候不需要进行任何操作，显然有 dp[i] [j] = dp[i-1] [j-1]。（别忘了 dp[i] [j] 的含义哈）。
二、如果我们 word1[i] 与 word2 [j] 不相等，这个时候我们就必须进行调整，而调整的操作有 3 种，我们要选择一种。三种操作对应的关系试如下（注意字符串与字符的区别）：
（1）、如果把字符 word1[i] 替换成与 word2[j] 相等，则有 dp[i] [j] = dp[i-1] [j-1] + 1;
（2）、如果在字符串 word1末尾插入一个与 word2[j] 相等的字符，则有 dp[i] [j] = dp[i] [j-1] + 1;
（3）、如果把字符 word1[i] 删除，则有 dp[i] [j] = dp[i-1] [j] + 1;
那么我们应该选择一种操作，使得 dp[i] [j] 的值最小，显然有
dp[i] [j] = min(dp[i-1] [j-1]，dp[i] [j-1]，dp[[i-1] [j]]) + 1;
于是，我们的关系式就推出来了，
最长上升子序列
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
向下向右走的动态规划
这类经典的题目需要注意以下几点：
1：你可以使用滚动数组，滚动数组的形式是dp[j] = dp[j] + dp[j-1]; 这个形式是跟 dp[i][j]=dp[i][j-1]+dp[i-1][j] 有关的；
这个dp[j-1]是更新过的,就是这行，相当于dp[i][j-1],而dp[j] 是没有更新过的，就是上一行老值，相当于dp[i-1][j]
120. 三角形最小路径和
2：你也可以使用二维数组，注意申请数组时容量大小要不要比size 大1？就是看最后要不要考虑length+1这个元素
3：边界条件的判断中，格外注意一下最上边一行，最右边一列，以及开头元素的特殊处理，这些可以通过在for 循环中加 if 条件判断，也可以在之前额外加一个循环单独处理这些边界条件，最后从1开始，
4：有些题目（勇士救公主174. 地下城游戏）从开头进行动态规划比较复杂，可以换个思路从终点往起点往回推