第一阶段：基础递归理解「返回值+1」的结构
- Leetcode 104. 二叉树的最大深度
https://leetcode.cn/problems/maximum-depth-of-binary-tree/
目标：理解如何从叶子往回返回「深度」值
关键词：return 1 + max(dfs(left), dfs(right))
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
dep=max(root.right,root.left)+1
return dep报错。。。
。。。。。
傻逼没加迭代。。。。不知道在些什么
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
dep=max(self.maxDepth(root.right),self.maxDepth(root.left))+1
return dep- Leetcode 733. 图像渲染（Flood Fill）
https://leetcode.cn/problems/flood-fill/
目标：理解如何用 DFS 走遍一张图
关键词：探索四个方向，递归不返回值，但有“已访问”逻辑
非常的简单嗷，闭眼写，然后就报错了。。。：
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
func=[(0,1),(0,-1),(1,0),(-1,0)]
m=len(image)
n=len(image)
old_color=image[sr][sc]
def dfs(r,c):
if image[r][c]==color or r >= m or r < m or c >= n or c < n :
return
if image[r][c] == old_color :
image[r][c] = color
for i,j in func:
dfs(r+i,c+j)
dfs(sr,sc)
return image边界条件错了，但是通过例只有170/253
def dfs(r,c):
if r>=m or r<0 or c >=n or c<0 or image[r][c]==color or image[r][c]!=old_color:
.....
........没休息好导致的，漏了一个小东西
上面的代码中俩个都是一样的
m=len(image)
n=len(image[0])✅ 第二阶段：路径型递归 + 返回路径长度
- Leetcode 329. 矩阵中的最长递增路径
https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/
目标：你现在研究的就是这个题目！
关键词：1 + dfs(...)，方向遍历 + 记忆化
写出来了，但是报错out of list，应该把判断长度的放在最前面
class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
m=len(matrix)
n=len(matrix[0])
mat=[[0]*n for _ in range(m)]
di=[(0,1),(0,-1),(1,0),(-1,0)]
def dfs(i,j,step):
if mat[i][j]!=0:
return mat[i][j]
if i>=m or j>=n or i<0 or j<0:
return step-1
cur_res=step
for o,k in di:
nxt=dfs(i+o,j+k,step+1)
if nxt>cur_res:
cur_res=nxt
return cur_res
res=-inf
for i in range(m):
for j in range(n):
cur_res=dfs(i,j,1)
if cur_res>=res:
res=cur_res
改了一版本，加上了限制和判断，还是报错。。。尝试debug
。。。。还是没改对，记录下来，下次再写。。。
先补上一共正确版本：
（算法有不同的写法，全忘掉再重新写就好了orz
class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
m=len(matrix)
n=len(matrix[0])
mat=[[0]*n for _ in range(m)]
di=[(0,1),(0,-1),(1,0),(-1,0)]
def dfs(i,j,pre):
if i>=m or j>=n or i<0 or j<0 or pre>=matrix[i][j]:
return 0
if mat[i][j]!=0:
return mat[i][j]
cur_res=0
for o,k in di:
cur_res=max(cur_res,dfs(i+o,j+k,matrix[i][j])+1)
mat[i][j]=cur_res
return cur_res
res=-inf
for i in range(m):
for j in range(n):
res=max(res,dfs(i,j,-inf))
return res
- Leetcode 62. 不同路径（递归版）
https://leetcode.cn/problems/unique-paths/
目标：练习“从当前格子出发有几条路径到终点”
关键词：return dfs(i+1,j) + dfs(i,j+1)
这题下次再做
- Leetcode 198. 打家劫舍（带返回值的DP递归）
https://leetcode.cn/problems/house-robber/
目标：理解“当前选择 = 子问题最大值 + 当前值”
关键词：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
时刻记得当前的dfs和dp要干啥！
class Solution:
def rob(self, nums):
n=len(nums)
memo = {}
def dfs(i):#在第i个做什么操作？返回什么？
if i >=n:
return 0
if i in memo:
return memo[i]
cur=nums[i]+dfs(i+2)#吃当前的
nocur=dfs(i+1)#吃下一个，不吃当前的
memo[i]=max(cur,nocur)
return memo[i]
return dfs(0)
def robdp(self,nums):#dp[i]=第i个的最大金额
#
n=len(nums)
dp=[0]*(n+1)#dp[i]=max(dp[i-2]+nums[i],dp[i-1])
#dp[0]=nums[0],dp[1]=max(nums[0],nums[1])
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2,n):
dp[i]=max(dp[i-2]+nums[i],dp[i-1])
return dp[n-1]
#nums = [2,7,9,3,1]
nums = [1,2,3,1]
r=Solution().rob(nums)
dp=Solution().robdp(nums)
print(r)
print(dp)