|
?在知乎上看到有人写得不错，最近也刚好开始在刷LC了，所以把自己解题时想到的写下来。
动态规划，利用历史记录，来避免重复计算
这些历史记录，需要一些变量去保存，一般就是用一维数组/二维数组去保存。
-
定义数组的含义：我们定义好数组的元素的意思，这样就很好解题了 -
找出数组元素之间的关系：我们的目的是求n，那么我们可以用n-1， n-2的历史记录去求得n的value 这个是最难的一步，也就是把大问题拆成小问题，譬如n = n-1 + n-2 -
找到初始值，初始值不一定只有一个，有可能是多个，所以我们要细心找到某一些“数组里面的值” 是没办法通过找元素间的关系去求出来的（也就是所谓的不可以再细分了）
第一题：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
-
定义数组的含义，我们这里定义一个一维数组：dp[] -
我们的问题是青蛙跳上n级台阶总共有多少种跳法，于是我们定义dp[i]的含义就是跳上一个i级台阶一共有dp[i]种跳法，所以只要我们求得dp[n]的值就可以知道答案了 -
（我们先来分析第二步，定义一维数组这个就我觉得跟前进方向有关，因为只可以向前走，所以只管一个维度就好了。其次是含义，含义是根据命题来决定的，命题决定是啥，数组的含义就是啥，具体到问题可能是第x次/个/ 会怎么样怎么样，于是数组里面的x下标就是会怎么样。当然这里是一维，后面再看二维是怎么玩的）
-
找出数组之间的联系：动态规划问题就是通过子问题去解决大问题，所以这里的大小就存在一个联系，也就是数组之间的联系，最难的就是这个
-
对于这道题，由于情况可以选择跳一级，也可以选择跳两级，所以青蛙到达第 n 级的台阶有两种方式：一种是从第 n-1 级跳上来，一种是从第 n-2 级跳上来，由于我们是要算 所有可能的跳法的，所以有 dp[n] = dp[n-1] + dp[n-2]。 -
（这里她是怎想的，就是从当前开始往回想，我这一步可以是通过前一步的什么状态来的，根据题目给的条件，我们知道可以是n-1/n-2，这里就狠厉害了，然后是要计算所有可能的跳法，也就是复用了前面的数组了，因为我当前这一步，只管前一步的状态，不管前一步再之前的任何状态，所以我们可以直接套dp进去） -
找初始条件：这里就是要 仔细观察我们的数组上面，到底哪些下标是不可以通过递推出来的，也是用从当前状态开始往回想开始，例如dp[1] = dp[0] + dp[-1] ，现在我们来回到数组元素的定义 “dp[i]的含义就是跳上一个i级台阶一共有dp[i]种跳法” ，很明显，dp[0] 和 dp[-1] 都是不可以通过递推得来的，所以我们应该定义dp[1]的value作为初始值。 -
然后我们还要再多一个心眼，因为他一次可以跳一步/跳两步，dp[2] = dp[1] + dp[0]，这里其实也挺难的，因为心里没一谱，不知道初始状态找完了没有，大佬说只能多写题了。dp2既可以从0直接上来，也可以从0到1再到2，所以一般他有多个方向可以移动的话，多注意第二步是不是可以从多个方向来的就好了的（应该哈）
问题2：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？
这么一看，首先机器人可以走一个二维的路子，所以肯定是一个建立一个二维数组dp [ ] [ ]了
-
定义数组的含义（含义是根据命题来决定的，命题决定是啥，数组的含义就是啥，具体到问题可能是第x次/个/ 会怎么样怎么样，于是数组里面的x下标就是会怎么样。当然这里是一维，后面再看二维是怎么玩的） -
我自己就定义成 到达下标是i和j的时候共有dp[i] [j]条路径 这个对了 -
然后就是找关系，从当前 我处在第 下标是 （i，j） 的时候往前推，要么向下，就是从（i-1，j）来的，要么就是从（i，j-1）来的，于是 关系式可以写成：dp[i] [j] = dp[i-1] [j] + dp[i] [j-1] 然后也是不管我这之前的东西怎么来的，我只需要focus on当前这一步怎么来就好了，所以套上了dp。这个对了 -
找到初始值：从最开始的状态往回推：dp[0] [0] = dp[-1] [0] + dp[0] [-1] 很明显dp[0] [0] 需要我们定义出来，然后再写这个dp [0] [0]的时候，发现一个东西，就是我们上面说的 我们要把所有的初始值都找出来（某一些value不可以直接用递推表示出来）=> （递推式里面有两个元素，一个是dp[i-1] [j] 另一个是dp[i] [j-1]） => （只要这两个元素有其中一个没写出来，那么这个递推的目标（等式的左边）就应该称为一个初始值）=>（所以最左边一列（没有dp[i-1] [j]），最上面一行（dp[i] [j-1]）都是需要初始化的） -
所以 最左边一列 和 最上面一行 的value 都是1 ，然后由于向下走和向右走的步长都是1，且方向不一样，也就是其中一方不可以包括另外一方，于是没有像上一题那样 dp[2] = 2的情况。 这个也对了！
问题3：给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。
-
定义数组的含义，两个方向，那就是二维的数组dp[] [] -
dp[i] [j]为走到（i，j）下标时， 数字总和最少是多少（因为我是觉得题目怎么问我就怎么设定含义）这个对了 -
找出数组的关系：从当前出发：dp[i] [j] = min( dp[i-1] [j] , dp[i] [j-1] ) + 自己的value 这个对了。 -
（这个不能盲目地和之前第一第二题一样地思考，因为前两题都是求路径和，当然用sum，在这里我们是想求min，所以我们要对可以通往当前时刻的路径做一个筛选，也就是做一个比较，这相当于选出一条路径了，然后再加上选择这条路径的成本，就是走到当前下标（i，j）的数字最少和了） -
找出初始值：也是从当前的状态出发，先看（0，0），肯定是需要初始化，然后左边一列，上面一排，也是需要初始化；移动也没有包含关系，所以不用考虑第一题dp[2]的情形
问题4：给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作：插入一个字符 删除一个字符 替换一个字符。
-
这个定义数组的维度就没前面那么直观了（我觉得是将word1的前n个字符换成word2前j个字符所需最少操作数）4*2 猜对了 -
怎么猜的，因为感觉字符的变换其实也是向下走，向右走的操作，向下走就是有两种情况，m*n （当前时刻m > n）的情况，就是n已经处理完了，剩下的m都是删除；然后另外一种情况就是m < n，这时候是m和n都同时走一步，也就是往右下方去处理？ 我自己感觉是这样所以才用二维数组。（但是理解错了） -
找元素之间的关系： -
之前的理解是错了，理解得还不够深入，确实m和n的大小关系是需要考虑的。但还需要判断当前的value是否相等，这是其一，第二还需要有 n > m的关系，这点也没考虑进去，所以其实一考虑进去，就很容易想到三个对应的操作，其实就是三种走法，正下方，正右方，还有右下方走，这就很灵性了，相当于在怎么走的基础上加了一层蒙版，要自己先理解了对了 数组的含义 才能更好地去理解三个操作。我觉得这就是一个套路了 -
所以（看答案） 当两个字符串都没有走完，判断是否相等，相等就加0，看下一个，看的这个操作是往右下方走；如果不想等，其实就是换，因为两个子串还没走完，所以也是往右下方走。于是dp[i] [j] = dp[i+1] [j+1] + 1 -
当被转换的字符串走完了，也就是出现n>m的情况，这时候没有其他操作，就是增加而已，所以dp[i] [j] = dp[i] [j-1] + 1 为什么是这个等式呢？因为i已经是m了，走到头了，没法往下走了，只能往右走 -
当转换模版的字符串走完了，也就是出现m>n的情况，这时候没有其他操作，就是删除而已，所以dp[i] [j] = dp[i-1] [j] + 1 为什么是这个等式呢？因为j已经是n了，走到头了，没法往下走了，只能往下走 -
所以 递推式应该怎么写，这里不是第一第二题的形式，问有多少种方式，有第三题那种约束条件存在（最少）。但因为其实除了元素相等每一步怎么走都是+1的操作，所以没有当前存在最小值的区别。但也是有可能这一点就是最小值的区别，怎么走只是限制了更新的方式，（也就是是否加一，我觉得还是有区别的）。 -
那我应该怎么把“value相等”的这个操作写在递推式里面呀？。。。想了半个小时，看答案吧 -
看了下代码，妈的就是个if判断，看来我把问题太高度化了，想用一条式子cover所有的情况 -
如果相等，咱们就 dp[i] [j] = dp[i-1] [j-1] 如果不相等，咱们就min( dp[i-1] [j-1]，dp[i] [j-1]，dp[i-1] [j] ) + 1 为什么需要min，就是防止譬如出现前一个是元素是相等的情况，可以把相等的路线给选出来 -
最后就是初始化value了，怎么想呢，都是第一列，第一行分别是0~m,0~n 也就是 全插入/全删除操作 （这个对了）
|