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许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
网站标题：LeetCode之动态规划-创新互联
文章源于：http://myzitong.com/article/iijes.html