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

另外有需要云服务器可以了解下创新互联cdcxhl.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。