麦塔 变种怎么做

荔蔻 柳儿变种，需

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式

下应该怎么做？

1. def unique_path(m, n):
   
2.     ret = []
   
3.     def dfs(i, j, cur):
   
4.         if i == m-1 and j == n-1:
   
5.             ret.append(cur[:])
   
6.             return
   
7.         if i < m-1: dfs(i+1, j, cur + [(i+1, j)])
   
8.         if j < n-1: dfs(i, j+1, cur + [(i, j+1)])
   
9.    
   
10.     dfs(0, 0, [(0, 0)])
    
11.     return ret

复制代码

时间复杂度我个人想的是O(2^(m+n-2)) 或者O(2^(m+n)), 因为对于每一个格子都要做一次decision，除了最后一列和最后一行。-2可以认为是常数忽略不计。
空间复杂度的话因为记录每一条path，所以是O(m+n) * (m+n-2)! / (m-1)!(n-1)! 其中(m+n)是每一条path的长度，后面的factorial是ret的长度。

匿名用户 发表于 2025-2-5 20:10
时间复杂度我个人想的是O(2^(m+n-2)) 或者O(2^(m+n)), 因为对于每一个格子都要做一次decision，除了最后一 ...

base case里的: ret.append(cur[:]);  因为copy current path, 这步花的时间应该是O(M+N), 这一步不用算在time compelxity里吗? total time complexity应该是O((m + n) * 2 ^ (m + n - 2))吧

CurtisAAA 发表于 2025-2-5 22:57
base case里的: ret.append(cur[:]);  因为copy current path, 这步花的时间应该是O(M+N), 这一步不用算 ...

时间复杂度应该和空间复杂度是一样的，因为每一步有效操作都是添path里的一个位置

类似生成所有的combination，用dfs在每一步枚举所有向下或者向右走的情况

匿名用户 发表于 2025-2-5 20:44
类似生成所有的combination，用dfs在每一步枚举所有向下或者向右走的情况

可以分析下时间复杂度和空间复杂度吗？

用普通的dfs (backtracking) 就行，这题本来是考dp的，为了不让你用dp就改了条件

诺亚方舟R 发表于 2025-2-5 20:50
用普通的dfs (backtracking) 就行，这题本来是考dp的，为了不让你用dp就改了条件

那backtracking怎么存之前算过的状态呢？

CurtisAAA 发表于 2025-2-5 22:57
base case里的: ret.append(cur[:]);  因为copy current path, 这步花的时间应该是O(M+N), 这一步不用算 ...

你说的是对的！大佬牛逼！

返回的形式是坐标的list吗

匿名用户 发表于 2025-2-6 17:11
返回的形式是坐标的list吗

是路径类似于这种“RLUD...."
R:Right
L: Left
U:Up
D:Down