动态规划,无非就是利用历史记录,来避免我们的重复计算。
- 最优子结构。最优子结构指的是问题的最优解包含子问题的最优解。反过来说,我们可以通过子问题的最优解来推导出问题的最优解。或者理解为后面阶段的状态可以由前面阶段的状态推导出来。
- 无后效性。在推导后面阶段的状态的时候,我们只关心前面阶段的状态值,不关心这个状态是怎么一步步推导出来的。同时,某阶段的状态值一旦确定,就不受之后阶段的决策影响。
- 重复子问题。不同的决策序列,到达某个相同的阶段时,可能会产生重复的状态。
动态规划三大步骤
- 第一步骤:定义数组元素的含义,上面说了,我们会用一个数组,来保存历史数组,假设用一维数组 dp[] 吧。这个时候有一个非常非常重要的点,就是规定这个数组元素的含义,例如 dp[i] 是代表什么意思?
- 第二步骤:找出状态转移方程。当我们要计算 dp[n] 时,是可以利用 dp[n-1],dp[n-2]…..dp[1],来推出 dp[n] 的,也就是可以利用历史数据来推出新的元素值,所以我们要找出数组元素之间的关系式,例如 dp[n] = dp[n-1] + dp[n-2],这个就是他们的关系式了。
- 第三步骤:找出初始值。学过数学归纳法的都知道,虽然我们知道了数组元素之间的关系式,例如 dp[n] = dp[n-1] + dp[n-2],我们可以通过 dp[n-1] 和 dp[n-2] 来计算 dp[n],但是,我们得知道初始值啊,例如一直推下去的话,会由 dp[3] = dp[2] + dp[1]。而 dp[2] 和 dp[1] 是不能再分解的了,所以我们必须要能够直接获得 dp[2] 和 dp[1] 的值,而这,就是所谓的初始值。
案例
leetcode 70 Climbing Stairs
1 | You are climbing a stair case. It takes n steps to reach to the top. |
- 定义数组元素的含义
我们就定义 dp[i] 的含义为:跳上一个 i 级的台阶总共有 dp[i] 种跳法。 - 找出数组元素间的关系式
青蛙到达第 n 级的台阶有两种方式: 从第 n-1 级跳上来 和 从第 n-2 级跳上来。因此关系式为: - 找出初始条件
dp[0] = 0. dp[1] = 1. 即 n <= 1 时,dp[n] = n.
1 | class Solution: |
leetcode 62 Unique Paths
1 | 问题描述: |
- 定义数组元素的含义
当机器人从左上角走到(i, j) 这个位置时,一共有 dp[i][j] 种路径 - 找出关系数组元素间的关系式
- 找出初始值
- dp[0][0…n-1] = 1; // 相当于最上面一行,机器人只能一直往左走
- dp[0…m-1][0] = 1; // 相当于最左面一列,机器人只能一直往下走
1 | class Solution: |
leetcode 64 Minimum Path Sum
1 | 问题描述: |
- 定义数组元素的含义
当机器人从左上角走到(i, j) 这个位置时,最小的路径和是 dp[i][j] - 找出关系数组元素间的关系式
由于机器人可以向下走或者向右走,所以有两种方式到达:
- 一种是从 (i-1, j) 这个位置走一步到达
- 一种是从(i, j - 1) 这个位置走一步到达
不过这次不是计算所有可能路径,而是计算哪一个路径和是最小的,那么我们要从这两种方式中,选择一种,使得dp[i][j] 的值是最小的,显然有:
- 找出初始值
- dp[0][j] = arr[0][j] + dp[0][j-1]; // 相当于最上面一行,机器人只能一直往左走
- dp[i][0] = arr[i][0] + dp[i][0]; // 相当于最左面一列,机器人只能一直往下走
1 | class Solution: |
leetcode 72 Edit Distance
1 | Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2. |
- 定义数组元素的含义
当字符串 word1 的长度为 i,字符串 word2 的长度为 j 时,将 word1 转化为 word2 所使用的最少操作次数为 dp[i][j] - 找出关系数组元素间的关系式
比起其他题,这道题相对比较难找一点,但是,不管多难找,大部分情况下,dp[i][j] 和 dp[i-1] [j]、dp[i] [j-1]、dp[i-1] [j-1] 肯定存在某种关系。因为我们的目标就是,从规模小的,通过一些操作,推导出规模大的。对于这道题,我们可以对 word1 进行三种操作:- 插入一个字符
- 删除一个字符
- 替换一个字符
- 如果我们 word1[i] 与 word2 [j] 相等,这个时候不需要进行任何操作。
- 如果我们 word1[i] 与 word2 [j] 不相等,这个时候我们就必须进行调整,而调整的操作有 3 种,我们要选择一种。三种操作对应的关系试如下(注意字符串与字符的区别):
- 如果把字符 word1[i] 替换成与 word2[j] 相等,则有
- 如果在字符串word1末尾插入一个与 word2[j] 相等的字符,则有:
- 如果把字符 word1[i] 删除,则有:那么我们应该选择一种操作,使得 dp[i] [j] 的值最小,显然有:
- 找出初始值
我们的初始值是计算出所有的 dp[0] [0…n] 和所有的 dp[0…m][0]。这个还是非常容易计算的,因为当有一个字符串的长度为 0 时,转化为另外一个字符串,那就只能一直进行插入或者删除操作了。
1 | class Solution: |
reference from https://zhuanlan.zhihu.com/p/91582909