LeetCode之动态规划

　　Easy难度

　　Easy难度的都是一维DP，前面几道都是我们在学习dp的时候经常会遇到的例题。我认为dp的关键在于最优子结构的选择，最优子结构选择好了对应的状态转移就可以很容易的求解。建议把一些常用的最优子结构背下来(就跟当初背快排一样)，遇到类似的题目直接套用或者改变就好了。我的dp解题思路为 确定使用动态规划->确定最优子结构->确定状态转移方程->确定边界条件。动态规划并不是一种具体的解题方法，没有万能的公式可以套，而是一种解题的思维方法。

　　53. 最大子序和

　　分析：对于包含负数的求和容易陷入局部最优解而忽略全局最优解。

　　最优子结构：假设dp[i]表示以j结尾的最大子序列，也可以假设dp[i,j]为以i为起点j为终点的最大子序和，这种子结构明显比第一种复杂。

　　状态转移方程：最优子结构确定后可以确定状态转移方程了，假设i-1时的sum为正数，那么以i结尾的子序和为dp[i-1] + nums[i];如果当前sum为负数，那么不论nums[i]是正是负，加上一个负数之后都会减小，直接不加就完事了。因此状态转移方程为：dp[i]=max(dp[i-1] + nums[i], nums[i])

　　class Solution:

　　def maxSubArray(self, nums: List[int]) -> int:

　　dp = []

　　for i in range(len(nums)):

　　if i == 0:

　　dp.append(nums[i])

　　else:

　　dp.append(max(dp[i-1] + nums[i], nums[i]))

　　return max(dp)

　　70. 爬楼梯

　　分析: 一维dp还有一种简单的解法就是采用数学归纳法，首先计算前几项，然后归纳出一个一般通项。这里不需要严格证明，一般归纳的结果都是正确的，这里用这种方法作为解法。

　　最优子结构：对于一级台阶i，最后一步可能有两种情况，即从i-1上来，或者从i-2上来。

　　状态转移方程：采用数学归纳法：假设台阶数为n，方法数为dp

　　n = 1, dp[1] = 1

　　n = 2, dp[2] = 2

　　n = 3, dp[3] = 3 (111,12, 21)

　　n = 4, dp[4] = 5 (1111,121,211,112, 22)

　　容易发现 dp[i] = dp[i-1] + dp[i-2]

　　class Solution:

　　def climbStairs(self, n: int) -> int:

　　dp = [0, 1, 2]

　　i = 3

　　while i <= n:

　　dp.append(dp[i-1] + dp[i-2])

　　i = i + 1

　　return dp[n]

　　Medium难度

　　Easy难度的都是一维DP，到了Medium难度一般都是二维DP了或者有条件的一维DP。好的讲解动态规划的文章都只介绍了一维的DP，导致看完之后觉得很简单，到实际做起题来发现无从下手。二维DP的矩阵，当前dp[i,j]一般与三个值有关，即 dp[i-1][j], dp[i][j-1]和dp[i-1][j-1]。

　　62. 不同路径

　　分析：

　　1. 状态转移方程：到达终点可以分成两部分，第一部分从终点上方到达终点如红线所示，或者从终点左边到达终点如蓝线所示。那么到达终点的路径总数就等于红线总数加上蓝线总数(因为不可以斜着走)，因此状态转移方程为 dp[i][j] = dp[i-1][j] + dp[i][j-1]

　　2. 初始条件： 终点和起点重合时候只有一条路径，因此dp[1][1] = 1

　　class Solution:

　　def uniquePaths(self, m: int, n: int):

　　dp = [([0] * (n+1)) for i in range(m+1)] # create 2d array

　　for i in range(1, m+1):

　　for j in range(1, n+1):

　　if i == 1 and j == 1:

　　dp[i][j] = 1

　　else:

　　dp[i][j] = dp[i-1][j] + dp[i][j-1]

　　return dp[m][n]

　　P.S.：二维DP一般DP矩阵会比原始数据大一圈，一是为了符合真实环境，二是DP很多初始时刻值都为0

　　63. 不同路径 II

　　分析：

　　1. 状态转移方程：这道题和上面一道题类似，只不过加了一些限定条件。如图所示，如果终点上方存在障碍物，那么从终点上面的路径将全部失效，如果左边上方存在障碍物，那么从终点左边的路径将全部失效。而有没有障碍物已经给出，因此状态转移方程为： dp[i][j] = dp[i-1][j] * (1 - obstacleGrid[i-2][j-1]) + dp[i][j-1] * (1 - obstacleGrid[i-1][j-2])

　　2. 初始条件： 终点和起点重合时候只有一条路径，因此dp[1][1] = 1

　　3. 特殊情况：当障碍物在终点时，无论多大，路径都不存在

　　class Solution:

　　def uniquePathsWithObstacles(self, obstacleGrid):

　　m = len(obstacleGrid)

　　n = len(obstacleGrid[0])

　　if obstacleGrid[m-1][n-1] == 1:

　　return 0

　　dp = [([0] * (n+1)) for i in range(m+1)]

　　for i in range(1, m+1):

　　for j in range(1, n+1):

　　# print(i,j)

　　if i == 1 and j == 1:

　　dp[i][j] = 1 - obstacleGrid[i-1][j-1]

　　else:

　　dp[i][j] = dp[i-1][j] * (1 - obstacleGrid[i-2][j-1]) + dp[i][j-1] * (1 - obstacleGrid[i-1][j-2])

　　return dp[m][n]

　　64. 最小路径和

　　分析：这题和上面几题类似

　　1. 状态转移方程：如图所示，假设只有矩阵[[1,3],[1,5]]，那么以5作为终点的话有两条路径，一条从上方过来，另一条从左边过来。由于题目要求最小路径，因此选取红线和蓝线中的较小者，加上该点的值就是该点作为终点DP的值。因此，状态转移方程为： dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1]

　　2. 边界条件：当只有一行时，该路径为这一行的和 dp[i][j] = dp[i][j-1] + grid[i-1][j-1];只有一列时，该路径为这一列的和 dp[i][j] = dp[i-1][j] + grid[i-1][j-1]

　　class Solution:

　　def minPathSum(self, grid):

　　m = len(grid)

　　n = len(grid[0])

　　dp = [([0] * (n+1)) for i in range(m+1)]

　　for i in range(1, m+1):

　　for j in range(1, n+1):

　　if i == 1:

　　dp[i][j] = dp[i][j-1] + grid[i-1][j-1]

　　elif j == 1:

　　dp[i][j] = dp[i-1][j] + grid[i-1][j-1]

　　else:

　　dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1]

　　return dp[m][n]

　　96. 不同的二叉搜索树

　　分析：一维DP，不过状态转移方程有点复杂

　　1. 状态转移方程： 本题是在树结构下的DP，首先我们可以知道dp[1] = 1, dp[2] = 2, dp[3] = 5， 看上去没有任何联系。这道题一开始一头雾水，因为找不到子结构。在树的背景下就要考虑树结构的特点。一个二叉树分为左子树和右子树，而左右子树的元素数为n-1(减去根节点)。那么很容易想到将n-1分解成两个数的和，这两个数分别为左右子树元素数目。左右子树元素必定少于n，那么就可以查表找到对应的搜索树数目，分析到这子结构就确定了。下面看状态转移方程，以n=2为例，如图所示

　　当n=2时，有两种情况，以1为根节点，那么剩余元素2。此时左子树只有0个元素，因此二叉搜索树总数为dp[0]，右子树有1个元素，二叉搜索树总数为dp[1];另一种是以2为根节点，此时情况与以1为根节点情况相反。因此可以得出状态转移方程为

　　class Solution:

　　def numTrees(self, n: int) -> int:

　　dp = [0] * (n+1)

　　dp[0] = 1

　　dp[1] = 1

　　for i in range(2, n+1):

　　for j in range(i):

　　dp[i] += dp[i-1-j] * dp[j]

　　return dp[-1]

　　120. 三角形最小路径和

　　分析：自底向上的DP

　　1. 状态转移方程：这道题如果都是整数那么会简单很多，引入了负数就需要考虑到所有情况。因此需要计算所有可能性的值，采用自底向上的方法。从倒数第二层开始，计算每一层所有可能的最小值。那么，第二层所有可能最小值如图所示为[7,6,10]

　　由此可得，状态转移方程为 dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]。

　　class Solution:

　　def minimumTotal(self, triangle):

　　n = len(triangle)

　　dp = triangle[-1]

　　i = n-2

　　while i >=0:

　　j = 0无锡人流医院 http://www.bhnkyy39.com/

　　while j <= len(triangle[i])-1:

　　dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]

　　j += 1

　　i -= 1

　　return dp[0]

　　304. 二维区域和检索 - 矩阵不可变

　　分析：303. 区域和检索 - 数组不可变的基础之上，扩充到二维

　　状态转移方程：矩阵可以分解成一行一行来看，对于被选中的一行来说，我们假设row_dp[j]表示这一行截止到j的所有元素之和。那么选中局限区域内的值为row_dp[col2] - row_dp[col1-1]。如图所示，红色框出来的那一行row_dp = [1,3,3,4,9],被选中区域的值为row_dp[3] - row_dp[0] = 4 - 1 = 3。因此状态转移方程为：row_dp[j] = row_dp[j-1] + matrix[i][j]。对每一行都这样处理就可以得到整个矩阵的dp

　　class NumMatrix:

　　def __init__(self, matrix):

　　m = len(matrix)

　　if m == 0:

　　self.dp = None

　　return

　　n = len(matrix[0])

　　dp = []

　　for i in range(m):

　　row_dp = [matrix[i][0]]

　　for j in range(1, n):

　　row_dp.append(row_dp[j-1] + matrix[i][j])

　　dp.append(row_dp)

　　self.dp = dp

　　def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:

　　result = 0

　　i = row1

　　while i <= row2:

　　if col1 != 0:

　　result += self.dp[i][col2] - self.dp[i][col1-1]

　　else:

　　result += self.dp[i][col2]

　　i += 1

　　return result