算法题记录Day1

2025/7/3 算法算法动态规划记忆化 DFS 中等题

题目1

一个整数矩阵，输出最长严格的递增路径的长度。每个单元格，可以往上，下，左，右四个方向移动。不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例 1:

输入:

nums = [ [9,9,4], [6,6,8], [2,1,1] ]

输出:

解释: 最长递增路径为 [1, 2, 6, 9]。

示例 2:
输入:

nums = [ [3,4,5], [3,2,6], [2,2,1] ]

输出:

解释: 最长递增路径是 [3, 4, 5, 6]。
注意不允许在对角线方向上移动。

思路

第一眼看见题，想着使用回溯加剪枝（新建一个矩阵用于存储该位置的最大长度）写一版代码如下：

nums = [ [9,9,4], [6,6,8], [2,1,1] ]

m=len(nums)
mar_nums=[[0]*m]*m
fx=[(0,1),(1,0),(0,-1),(-1,0)]#右，下，左，上

def dfs(i,j,pre):
    if i<0 or j<0 or i>m or j>m:#边界条件
        return
    if nums[i][j] < pre:#当前的大于上一个的
        return
    for o,k in fx:#遍历四个方向
        dfs(i+o,j+k,nums[i][j])

maxnum=-10
for i in range(0,m):
    for j in range(0,m):
        mar_nums[i][j]=dfs(i,j,-10)
        if maxnum < mar_nums[i][j]:
            maxnum=mar_nums[i][j]

print(maxnum)

太久忘了dfs怎么写了。。。。

场外援助一下


def dfs(i,j,pre,step):
    if i<0 or j<0 or i>m or j>m:#边界条件
        return
    if nums[i][j] < pre : #当前的大于上一个的
        return
    for o,k in fx:#遍历四个方向
        dfs(i+o,j+k,nums[i][j],step+1)

额外加一个参数传递step

ps：边界条件都是m是因为是矩阵

。。。。然后运行报错了。。。。

RecursionError: maximum recursion depth exceeded in comparison

请gpt老祖出山

def dfs(i,j,pre,step):
    if i<0 or j<0 or i>=m or j>=m:#边界条件
        return step-1
    if nums[i][j]<=pre:#当前的大于上一个的
        return step-1
    max_len = step
    for o, k in fx:
        max_len = max(max_len, dfs(i + o, j + k, nums[i][j], step + 1))
    return max_len

max_len留的应该是最大长度，

优化版本的记忆化搜索：

nums = [ [9,9,4], [6,6,8], [2,1,1] ]

m = len(nums)
n = len(nums[0])
mar_nums = [[0]*n for _ in range(m)]  # 用于记忆化，记录每个格子的最长路径
fx = [(0,1),(1,0),(0,-1),(-1,0)]  # 右、下、左、上

def dfs(i, j):
    if mar_nums[i][j] != 0:
        return mar_nums[i][j]  # 已计算过，直接返回

    max_len = 1  # 至少包含当前这个点
    for dx, dy in fx:
        ni, nj = i + dx, j + dy
        if 0 <= ni < m and 0 <= nj < n and nums[ni][nj] > nums[i][j]:
            max_len = max(max_len, 1 + dfs(ni, nj))  # 递归搜索

    mar_nums[i][j] = max_len  # 记忆化存储
    return max_len

maxnum = 0
for i in range(m):
    for j in range(n):
        maxnum = max(maxnum, dfs(i, j))

print("最长递增路径长度为：", maxnum)

通过下面的进行记忆化，剪枝操作

    if mar_nums[i][j] != 0:
        return mar_nums[i][j]  # 已计算过，直接返回

总结

DFS动态规划记得返回

回溯框架：

def backtracking(path, choices):
    if termination_condition(path):
        result.append(path[:])  # 存放结果（注意要复制）
        return

    for choice in choices:
        if not is_valid(choice, path):  # 可选，剪枝
            continue

        path.append(choice)  # 做出选择
        backtracking(path, choices)  # 递归
        path.pop()  # 回溯，撤销选择

接下来练习的题单：（来源于chagpt）

✅ 第一阶段：基础递归理解「返回值+1」的结构
1. Leetcode 104. 二叉树的最大深度
https://leetcode.cn/problems/maximum-depth-of-binary-tree/
目标：理解如何从叶子往回返回「深度」值
关键词：return 1 + max(dfs(left), dfs(right))

Leetcode 733. 图像渲染（Flood Fill）
https://leetcode.cn/problems/flood-fill/
目标：理解如何用 DFS 走遍一张图
关键词：探索四个方向，递归不返回值，但有“已访问”逻辑
（这个虽然不加1，但会练你方向遍历和边界剪枝）

✅ 第二阶段：路径型递归 + 返回路径长度
3. Leetcode 329. 矩阵中的最长递增路径
https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/
目标：你现在研究的就是这个题目！
关键词：1 + dfs(...)，方向遍历 + 记忆化

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])

✅ 第三阶段：通用回溯 + 路径长度统计（练回溯框架）
6. Leetcode 17. 电话号码的字母组合
https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
目标：练习标准回溯框架（递归 + 回溯）
关键词：path.append(...) -> backtrack(...) -> path.pop()

Leetcode 46. 全排列
https://leetcode.cn/problems/permutations/
目标：更熟练回溯法中“选择-递归-撤销”的流程
关键词：构造路径、遍历集合、回退

✅ 加餐题（深度或路径最值递归）：
8. Leetcode 687. 最长同值路径
https://leetcode.cn/problems/longest-univalue-path/
目标：dfs 过程中计算“跨越左右子树的路径长度”，非常典型的 return 1 + dfs(...) 问题。

LOADING

算法题记录Day1

题目1

思路

总结