【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总（2）https://developer.aliyun.com/article/1536619
不同路径1
class Solution: def uniquePaths(self, m: int, n: int) -> int: dp = [[0 for i in range(n)] for _ in range(m)] for i in range(m): dp[i][0] = 1 for j in range(n): dp[0][j] = 1 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]
不同路径2
class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int: m = len(obstacleGrid) n = len(obstacleGrid[0]) zero_loc = {(i,j) for i in range(m) for j in range(n) if obstacleGrid[i][j] == 1} dp = [[0] * n for i in range(m)] for i in range(m): # 初始化第一列，只要碰到一个1，那么后边都无法走到 if obstacleGrid[i][0] == 1: break dp[i][0] = 1 for j in range(n): #初始化第一行，只要碰到一个1，那么后边都无法走到 if obstacleGrid[0][j] == 1: break dp[0][j] = 1 for i in range(1,m): for j in range(1,n): if (i,j) in zero_loc: dp[i][j] = 0 else: dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[-1][-1] class Solution: def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int: m = len(obstacleGrid) n =len(obstacleGrid[0]) if obstacleGrid[0][0] == 1 or obstacleGrid[-1][-1] == 1: return 0 dp = [[0] * n for _ in range(m)] for i in range(m): if obstacleGrid[i][0] == 0: dp[i][0] = 1 else: break for j in range(n): if obstacleGrid[0][j] == 0: dp[0][j] = 1 else: break for i in range(1,m): for j in range(1,n): if obstacleGrid[i][j] == 1: dp[i][j] = 0 continue dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[-1][-1]
不同路径3（回溯）
class Solution: def uniquePathsIII(self, grid: List[List[int]]) -> int: # 注意每一个无障碍的格子都需要通过一次 start_x = 0 start_y = 0 steps = 1 m = len(grid) n = len(grid[0]) # 遍历获取起始位置和统计总步数 for i in range(m): for j in range(n): if grid[i][j] == 1: start_x = i start_y = j continue if grid[i][j] == 0: steps += 1 def DFS(x,y,cur_step, grid): # 排除越界的情况和遇到障碍的情况 if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] == -1: return 0 if grid[x][y] == 2: # 走到2的位置，且步数为0，表示经过了所有的无障碍格子，是一种方案 return 1 if cur_step == 0 else 0 grid[x][y] = -1 # 将已经走过的标记为障碍 res = DFS(x - 1, y, cur_step - 1, grid) + DFS(x + 1, y, cur_step - 1, grid) \ + DFS(x, y - 1, cur_step - 1, grid) \ + DFS(x, y + 1, cur_step - 1, grid) # 回溯 grid[x][y] = 0 return res return DFS(start_x,start_y,steps,grid)
零钱兑换1
class Solution: def coinChange(self, coins: List[int], amount: int) -> int: #dp[i] = x 表示金额i最少需要x个金币 dp = [amount + 1 for i in range(amount + 1)] dp[0] = 0 for i in range(amount+1): for coin in coins: if i - coin < 0: continue dp[i] = min(dp[i],dp[i-coin] + 1) if dp[amount] == amount + 1: return -1 else: return dp[amount]
零钱兑换2
class Solution: def change(self, amount: int, coins: List[int]) -> int: # 子问题:对于硬币从0到k，我们必须使用第k个硬币的时候，当前金额的组合数 # 状态数组DP[i]表示对于第k个硬币能凑的组合数 # 转移方程DP[i] = DP[i] + DP[i-k] dp = [0] * (amount + 1) dp[0] = 1 for coin in coins: for x in range(coin, amount + 1): dp[x] += dp[x - coin] return dp[amount]
最大正方形
class Solution: def maximalSquare(self, matrix: List[List[str]]) -> int: # 用 dp(i, j) 表示以 (i, j)为右下角，且只包含 1的正方形的边长最大值 if len(matrix) == 0 or len(matrix[0]) == 0: return 0 maxSide = 0 rows, columns = len(matrix), len(matrix[0]) dp = [[0] * columns for _ in range(rows)] for i in range(rows): for j in range(columns): if matrix[i][j] == '1': if i == 0 or j == 0: dp[i][j] = 1 else: dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 maxSide = max(maxSide, dp[i][j]) maxSquare = maxSide * maxSide return maxSquare
最大矩形
class Solution: def maximalRectangle(self, matrix: List[List[str]]) -> int: #时间复杂度 : O(NM)。每次对于N的迭代我们会对M迭代常数次 if not matrix: return 0 m = len(matrix) n = len(matrix[0]) left = [0] * n # initialize left as the leftmost boundary possible right = [n] * n # initialize right as the rightmost boundary possible height = [0] * n maxarea = 0 for i in range(m): cur_left, cur_right = 0, n # update height for j in range(n): if matrix[i][j] == '1': height[j] += 1 else: height[j] = 0 # update left for j in range(n): if matrix[i][j] == '1': left[j] = max(left[j], cur_left) else: left[j] = 0 cur_left = j + 1 # update right for j in range(n-1, -1, -1): if matrix[i][j] == '1': right[j] = min(right[j], cur_right) else: right[j] = n cur_right = j # update the area for j in range(n): maxarea = max(maxarea, height[j] * (right[j] - left[j])) return maxarea
最大子序和
class Solution: def maxSubArray(self, nums: List[int]) -> int: # dp[i] 表示以小标i为结尾的最大连续子序列的和dp[j] = max(nums[j],dp[j-1] + nums[j]) if len(nums) == 0: return 0 if len(nums) == 1: return nums[0] n = len(nums) dp = [float('-inf')] * n dp[0] = nums[0] for j in range(1,n): dp[j] = max(nums[j],dp[j-1] + nums[j]) return max(dp)
三角形最小路径和
#法一 class Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: n = len(triangle) f = [[0] * n for _ in range(n)] f[0][0] = triangle[0][0] for i in range(1, n): f[i][0] = f[i - 1][0] + triangle[i][0] for j in range(1, i): f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j] f[i][i] = f[i - 1][i - 1] + triangle[i][i] return min(f[n - 1]) #法二 class Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: n = len(triangle) f = [0] * n f[0] = triangle[0][0] for i in range(1, n): f[i] = f[i - 1] + triangle[i][i] for j in range(i - 1, 0, -1): f[j] = min(f[j - 1], f[j]) + triangle[i][j] f[0] += triangle[i][0] return min(f)
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总（4） https://developer.aliyun.com/article/1536622
