题解 | #不同路径的数目(一)#
https://www.nowcoder.com/practice/166eaff8439d4cd898e3ba933fbc6358
class Solution: def uniquePaths(self , m: int, n: int) -> int: # write code here if m == 1 or n == 1: return 1 a = [1]*n for i in range(m-1): for j in range(2,n+1): a[j-1] = a[j-1] + a[j-2] return a[n-1]
可以把空间复杂度缩减到O（min（n，m）），例如当n比m小时，第一行为全1，第二行算出来的值直接覆盖第一行，因为算第三行时用不到第一行，所以当第一轮循环结束a[i]是第二行的第i个值。
当m较小时就竖着算，从第一列到最后一列。时间复杂度还是O（mn）
原始一点点的解法 文章被收录于专栏
尽量不借助面向对象的思想，自己去实习具体过程
投递vivo等公司7个岗位 >