题目一（打卡）、
def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]: # 生成邻接表(Adjacency List) aList = [[] for _ in range(N)] for child, father in edges: aList[father].append(child) aList[child].append(father) # 计算每个节点的深度和以每个节点作为根节点的子树节点个数（包含根节点） # deepth: 节点深度 # count: 节点个数 deepth = [0] * N count = [0] * N def dfs(child, father): count[child] = 1 for grandson in aList[child]: if grandson != father: deepth[grandson] = deepth[child] + 1 dfs(grandson, child) count[child] += count[grandson] dfs(0, -1) answer = [0] * N answer[0] = sum(deepth) def dfs_a(child, father): for grandson in aList[child]: if grandson != father: # count[grandson]个节点需要少走一步，N - count[grandson]个节点需要多走一步 # answer[grandson] = answer[child] - count[grandson] + N - count[grandson] answer[grandson] = answer[child] + N - 2 * count[grandson] dfs_a(grandson, child) dfs_a(0, -1) return answer
DP入门：
题目二：
70. 爬楼梯
def climbStairs(self, n: int) -> int: # dp # dp[i]: 排到i阶梯有多少种爬法 dp = [-1 for _ in range(n+1)] dp[0] = dp[1] = 1 for i in range(2, n+1): dp[i] = dp[i-1] + dp[i-2] return dp[n]
题目三、
def minimumTotal(self, triangle: List[List[int]]) -> int: # 1.递归过程，存在重复子问题 # def dfs(i, j): # if i == len(triangle)-1: # return triangle[i][j] # return triangle[i][j] + min(dfs(i+1,j), dfs(i+1,j+1)) # return dfs(0, 0) # 2.记忆化搜索，解决重子问题 # memo = copy.deepcopy(triangle) # memo = [[-1 for _ in range(len(l))] for l in triangle] # def dfs(i, j): # if i == len(triangle)-1: # return triangle[i][j] # if memo[i][j] == -1: # memo[i][j] = triangle[i][j] + min(dfs(i+1,j), dfs(i+1,j+1)) # return memo[i][j] # return dfs(0, 0) # 3.动态规划 for i in range(len(triangle) - 2, -1, -1): for j in range(len(triangle[i])): triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]) return triangle[0][0]
题目四、
def minPathSum(self, grid: List[List[int]]) -> int: # 1.BFS 超时 # rows = len(grid) # cols = len(grid[0]) # dp = [[float('inf') for _ in range(cols)] for x in range(rows)] # queue = [(0,0)] # dp[0][0] = grid[0][0] # while queue: # i, j = queue.pop(0) # if i + 1 < rows: # dp[i+1][j] = min(dp[i+1][j], dp[i][j] + grid[i+1][j]) # queue.append((i+1, j)) # if j + 1 < cols: # dp[i][j+1] = min(dp[i][j+1], dp[i][j] + grid[i][j+1]) # queue.append((i, j+1)) # return dp[rows - 1][cols - 1] # 2.动态规划 # rows = len(grid) # cols = len(grid[0]) # for i in range(rows): # for j in range(cols): # if i == 0 and j == 0: # continue # elif i == 0: grid[i][j] += grid[i][j-1] # elif j == 0: grid[i][j] += grid[i-1][j] # else: grid[i][j] += min(grid[i][j-1], grid[i-1][j]) # return grid[-1][-1] # 3.递归 + 记忆化搜索 rows = len(grid) cols = len(grid[0]) memo = [[-1 for _ in range(cols)] for x in range(rows)] def dfs(i, j): if i == 0 and j == 0: return grid[0][0] if memo[i][j] == -1: if i == 0: memo[i][j] = grid[i][j] + dfs(i, j - 1) elif j == 0: memo[i][j] = grid[i][j] + dfs(i - 1, j) else: memo[i][j] = grid[i][j] + min(dfs(i-1, j), dfs(i, j - 1)) return memo[i][j] return dfs(rows - 1, cols - 1)
题目五、
def integerBreak(self, n: int) -> int: # 1.dfs + 记忆化搜索 # memo = [-1 for _ in range(n+1)] # def dfs(n): # if n == 1: # return 1 # if memo[n] == -1: # res = 0 # for i in range(1,n): # res = max(res, i * (n-i), i * dfs(n-i)) # memo[n] = res # return memo[n] # return dfs(n) # dp[i]: i 拆分之后可以获得的最大乘积 # 2.动态规划 dp = [0 for _ in range(n+1)] dp[1] = 1 dp[2] = 1 for i in range(3, n + 1): dp[i] = max(max(dp[i-2], i-2)*2, max(dp[i-3],i-3)*3) return dp[-1]
题目六、
def numSquares(self, n: int) -> int: dp = [0 for _ in range(n+1)] # 生成小于n的平方数列 squares = [ i*i for i in range(1, math.ceil(math.sqrt(n))+1)] for num in range(1, n+1): min_num = num for s in squares: if s > num: break if dp[num-s] + 1 < min_num: min_num = dp[num-s] + 1 dp[num] = min_num return dp[n]
题目七、
def rob(self, nums: List[int]) -> int: # 记忆化搜索 # lenth = len(nums) # memo = [-1 for _ in range(lenth)] # def dfs(index): # if index >= lenth: # return 0 # if memo[index] == -1: # res = 0 # for i in range(index, lenth): # res = max(res, nums[i] + dfs(i+2)) # memo[index] = res # return memo[index] # return dfs(0) # 动态规划(从后往前考虑) # dp[i] = max(dp[i], nums[index] + d[index+2]) # lenth = len(nums) # if lenth == 0: # return 0 # dp = [0 for _ in range(lenth)] # dp[lenth-1] = nums[lenth-1] # for i in range(lenth-1, -1, -1): # for index in range(i, lenth): # if index + 2 >= lenth: # dp[i] = max(dp[i], nums[index] + 0) # else: # dp[i] = max(dp[i], nums[index] + dp[index+2]) # return dp[0] # 动态规划(从前往后考虑) # dp[i] = max(dp[i-2]+nums[i], dp[i-1]) lenth = len(nums) if lenth == 0: return 0 elif lenth == 1: return nums[0] dp = [0 for _ in range(len(nums))] dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) for i in range(2, lenth): dp[i] = max(dp[i-2] + nums[i], dp[i-1]) return dp[-1]
题目八、
def rob(self, nums: List[int]) -> int: # 和一的不同，分解为两个子问题，分别进行动态规划 # 1. 偷第一家 2.不偷第一家 lenth = len(nums) if lenth == 0: return 0 elif lenth == 1: return nums[0] elif lenth == 2: return max(nums[0], nums[1]) # 抢第一个 dp0 = [0 for _ in range(len(nums))] dp0[0] = nums[0] dp0[1] = max(nums[0], nums[1]) for i in range(2, len(nums) - 1): dp0[i] = max(dp0[i-1], dp0[i-2] + nums[i]) # 不抢第一个 dp1 = [0 for _ in range(len(nums))] dp1[1] = nums[1] dp1[2] = max(nums[1], nums[2]) for i in range(3, len(nums)): dp1[i] = max(dp1[i-1], dp1[i-2] + nums[i]) return max(dp0[-2], dp1[-1])
题目九、
def rob(self, root: TreeNode) -> int: # 中序遍历 # dp[root] = [0,0] (root == None) # dp[root] = [max(dp[root.left]) + max(dp[root.right.left]), root.val + dp[root.left][0] + dp[root.right][0]] (root != None) def dfs(root): if not root: return [0, 0] l = dfs(root.left) r = dfs(root.right) return max(l) + max(r), root.val + l[0] + r[0] return max(dfs(root))