动态规划,无非就是利用历史记录,来避免我们的重复计算。
最优子结构 。最优子结构指的是问题的最优解包含子问题的最优解。反过来说,我们可以通过子问题的最优解来推导出问题的最优解。或者理解为后面阶段的状态可以由前面阶段的状态推导出来。
无后效性 。在推导后面阶段的状态的时候,我们只关心前面阶段的状态值,不关心这个状态是怎么一步步推导出来的。同时,某阶段的状态值一旦确定,就不受之后阶段的决策影响。
重复子问题 。不同的决策序列,到达某个相同的阶段时,可能会产生重复的状态。
动态规划三大步骤
第一步骤:定义数组元素的含义,上面说了,我们会用一个数组,来保存历史数组,假设用一维数组 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] 的值,而这,就是所谓的初始值。
案例
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Note: Given n will be a positive integer. Example 1: Input: 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps Example 2: Input: 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step
定义数组元素的含义 我们就定义 dp[i] 的含义为:跳上一个 i 级的台阶总共有 dp[i] 种跳法。
找出数组元素间的关系式 青蛙到达第 n 级的台阶有两种方式: 从第 n-1 级跳上来 和 从第 n-2 级跳上来。因此关系式为: \[dp[n] = dp[n-1] + dp[n-2]\]
找出初始条件 dp[0] = 0. dp[1] = 1. 即 n <= 1 时,dp[n] = n.
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution : def climbStairs (self, n: int ) -> int : if n <= 2 : return n dp = [-1 ] * (n+1 ) dp[0 ] = 0 dp[1 ] = 1 dp[2 ] = 2 for i in range (3 ,n+1 ): dp[i] = dp[i-1 ] + dp[i-2 ] return dp[-1 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 问题描述: A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). How many possible unique paths are there? Note: m and n will be at most 100. Example 1: Input: m = 3, n = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: 1. Right -> Right -> Down 2. Right -> Down -> Right 3. Down -> Right -> Right Example 2: Input: m = 7, n = 3 Output: 28
定义数组元素的含义 当机器人从左上角走到(i, j) 这个位置时,一共有 dp[i][j] 种路径
找出关系数组元素间的关系式 \[dp[i][j] = dp[i-1][j] + dp[i][j-1]\]
找出初始值
dp[0][0...n-1] = 1; // 相当于最上面一行,机器人只能一直往左走
dp[0...m-1][0] = 1; // 相当于最左面一列,机器人只能一直往下走
1 2 3 4 5 6 7 8 9 10 11 12 class Solution : def uniquePaths (self, m: int , n: int ) -> int : if not m or not n: return 1 dp = [[1 ] * n for i in range (m)] for i in range (1 ,m): for j in range (1 ,n): dp[i][j] = dp[i-1 ][j] + dp[i][j-1 ] return dp[-1 ][-1 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 问题描述: Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time. Example: Input: [ [1,3,1], [1,5,1], [4,2,1] ] Output: 7 Explanation: Because the path 1→3→1→1→1 minimizes the sum.
定义数组元素的含义 当机器人从左上角走到(i, j) 这个位置时,最小的路径和是 dp[i][j]
找出关系数组元素间的关系式 由于机器人可以向下走或者向右走,所以有两种方式到达:
一种是从 (i-1, j) 这个位置走一步到达
一种是从(i, j - 1) 这个位置走一步到达 不过这次不是计算所有可能路径,而是计算哪一个路径和是最小的 ,那么我们要从这两种方式中,选择一种,使得dp[i][j] 的值是最小的,显然有: \[dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + arr[i][j]\]
找出初始值
dp[0][j] = arr[0][j] + dp[0][j-1]; // 相当于最上面一行,机器人只能一直往左走
dp[i][0] = arr[i][0] + dp[i][0]; // 相当于最左面一列,机器人只能一直往下走
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution : def minPathSum (self, grid: List [List [int ]] ) -> int : m,n = len (grid),len (grid[0 ]) dp = [[0 ] * n for i in range (m)] dp[0 ][0 ] = grid[0 ][0 ] for i in range (1 ,n): dp[0 ][i] = grid[0 ][i] + dp[0 ][i-1 ] for j in range (1 ,m): dp[j][0 ] = grid[j][0 ] + dp[j-1 ][0 ] for i in range (1 ,m): for j in range (1 ,n): dp[i][j] = min (dp[i-1 ][j],dp[i][j-1 ]) + grid[i][j] return dp[-1 ][-1 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted on a word: Insert a character Delete a character Replace a character Example 1: Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e') Example 2: Input: word1 = "intention", word2 = "execution" Output: 5 Explanation: intention -> inention (remove 't') inention -> enention (replace 'i' with 'e') enention -> exention (replace 'n' with 'x') exention -> exection (replace 'n' with 'c') exection -> execution (insert 'u')
定义数组元素的含义 当字符串 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] 相等,这个时候不需要进行任何操作。 \[dp[i][j] = dp[i-1][j-1]\]
如果我们 word1[i] 与 word2 [j] 不相等,这个时候我们就必须进行调整,而调整的操作有 3 种,我们要选择一种。三种操作对应的关系试如下(注意字符串与字符的区别):
如果把字符 word1[i] 替换成与 word2[j] 相等,则有 \[dp[i][j] = dp[i-1][j-1] + 1\]
如果在字符串word1末尾插入一个与 word2[j] 相等的字符,则有: \[dp[i][j] = dp[i] [j-1] + 1\]
如果把字符 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\]
找出初始值 我们的初始值是计算出所有的 dp[0] [0...n] 和所有的 dp[0...m][0]。这个还是非常容易计算的,因为当有一个字符串的长度为 0 时,转化为另外一个字符串,那就只能一直进行插入或者删除操作了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution : def minDistance (self, word1: str , word2: str ) -> int : len_word2 = len (word2) len_word1 = len (word1) dp = [[0 ] * (len_word2+1 ) for i in range (len_word1+1 )] for j in range (1 ,len_word2+1 ): dp[0 ][j] = dp[0 ][j-1 ]+1 for i in range (1 ,len_word1+1 ): dp[i][0 ] = dp[i-1 ][0 ] + 1 for i in range (1 ,len (word1)+1 ): for j in range (1 ,len (word2)+1 ): if word1[i-1 ] == word2[j-1 ]: dp[i][j] = dp[i-1 ][j-1 ] else : dp[i][j] = min ([dp[i-1 ][j-1 ],dp[i][j-1 ],dp[i-1 ][j]]) + 1 return dp[-1 ][-1 ]
reference from https://zhuanlan.zhihu.com/p/91582909