【Leetcode Daily】62不同路径

发表于2025-11-06|更新于2025-11-06|力扣日常 | LeetcodeDaily

|总字数:260|阅读时长:1分钟|浏览量:

题目浅析

想查看原题可以点击题目链接。
简单地说，就是给一个 m*n 的网格，求从该网格的左上角到右下角有多少条路径。

思路分享

先划分子问题，一个不错的思路是考虑最后一步，（m-1，n-1）处是由（m-1，n-2）和（m-2，n-1）相加得出的，这样就算得到了子问题和状态转移方程，接下来转记忆化搜索（本题比较容易就直接递推了）再翻译成递推，进而优化空间。

https://leetcode.cn/problems/unique-paths/solutions/3062432/liang-chong-fang-fa-dong-tai-gui-hua-zu-o5k32/

代码解答（强烈建议自行解答后再看）

参考题解

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        f = [1]*n
        for i in range(1, m):
            for j in range(1, n):
                f[j] = f[j] + f[j-1]
        return f[n-1]

        # 基础递推
        # f = [[1]*n for _ in range(m)]
        # for i in range(1, m):
        #     for j in range(1, n):
        #         f[i][j] = f[i-1][j] + f[i][j-1]
        # return f[m-1][n-1]

文章作者: 陆爻齐-LuYaoQi

文章链接: http://hslix.github.io/posts/1dd88d10.html

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 LuYaoQi's Blogs！

Algorithm 动态规划

相关推荐

【Leetcode Daily】1143最长公共子序列

题目浅析想查看原题可以点击题目链接。简单地说，就是找到两个字符串的最长公共子序列（具体含义请看原题）长度。思路分享这是线性 DP 的经典题目，子序列由于是可以选择性的删除中间部分，所以计算两个字符串的公共子序列，可以分为多个子问题，具体分析如下： https://leetcode.cn/problems/longest-common-subsequence/solutions/2133188/jiao-ni-yi-bu-bu-si-kao-dong-tai-gui-hua-lbz5/ 对于两个字符串，每分别选的两个字符各有选和不选两种情况，也就是四种情况。在相等的情况下，肯定是两个都选好；不等时则两边各选一次。两边都不选一定不如上面三种情况。比如，有长 n、m 的两个字符串的最长公共子序列就是下面的子情况推导出来的：1. n-1、m；2. n、m-1；3. n-1、m-1. 前两个是字符匹配失败的场景，3...

【Leetcode Daily】72编辑距离

题目浅析想查看原题可以点击题目链接。简单地说，就是给两个字符串，求一个字符串到另一个字符串的最小编辑距离。所谓的编辑距离对一个字符串做插入、删除或更改一个字符算是一个单位的编辑距离。思路分享求一个字符串（长为 n）到另一个字符串（长为 m）的最小编辑距离，比如求从 horse 到 ros 的编辑距离 l，可以视为 hors 到 ros 的距离 l+1（因为左边字符串最右边删去一个字符）以此类推，可以得到记忆化递归的写法。重点记录由两个一维数组优化到一个一维数组中的思路，由于这里的状态由其位置的左、左上、上三个地方决定，所以必须从左向右遍历，如果直接这么做，会丢失坐上的数据，所以需要额外一个变量记录左上位置的数据，并及时更新。代码解答（强烈建议自行解答后再看）参考题解 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061class Solution: def...

【Leetcode Daily】300最长递增子序列

题目浅析想查看原题可以点击题目链接。简单地说，就是给你一个整型数组，你可以删除其中元素，但不改变元素顺序的情况下，制造出一个严格递增子数组，求该子数组的最长长度思路分享目前的 dp 无非两种思路：1. 选或不选；2. 枚举选哪个。选或不选形成的决策类似二叉树，而枚举选哪个会类似多叉树。前者很多时候划分为前 i 个元素的子问题，后者则是经常划分为以 i 下标为尾部的子问题。对于本题，可以分为以 i 下标为末尾的最长递增子序列长度。回到本题，首先尝试用记忆化回溯实现，如果采用思路一，那么在选择当前位的数字时，传递的过程中还需要报错前一个选择的数字下标（或者值），否则将无法保证选出来的序列严格递增；如果采用思路二，则是在枚举的循环内完成对不能满足严格递增情况的过滤，只要传递尾部下标即可。代码解答（强烈建议自行解答后再看）参考题解 1234567891011121314151617181920212223class Solution: def lengthOfLIS(self, nums: List[int]) -> int: #...

【Leetcode Daily】746使用最小花费爬楼梯

题目浅析想查看原题可以点击题目链接。简单地说，就是从第 0 或 1 开始爬楼梯，每个楼梯有花费，求爬到楼顶的最小花费。思路分享划分子问题，本题可以把爬到第 n 阶的最小花费变成爬到第 n-1 阶的最小花费问题，搞定这个就能写出来回溯dfs。然后再转递推。代码解答（强烈建议自行解答后再看）参考题解 123456789101112131415161718class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: n = len(cost) f = [0] * (n+1) f[0] = cost[0] f[1] = cost[1] for i in range(2, n): f[i] = min(f[i-1], f[i-2]) + cost[i] return min(f[n-1], f[n-2]) # @cache ...

【Leetcode Daily】3693爬楼梯II

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个 n 阶台阶，规定从第 i 级台阶跳到第 j 级台阶的成本定义为： costs[j] + (j - i)^2，求从 0 到台阶顶的最小成本。思路分享和【Leetcode Daily】746使用最小花费爬楼梯相似，也是属于“枚举选哪个”的部分代码解答（强烈建议自行解答后再看）参考题解 12345678910111213141516171819202122232425class Solution: def climbStairs(self, n: int, costs: List[int]) -> int: n = len(costs) f = [0] * (n+1) f[0] = 0 for i in range(1, n+1): f[i] = min(f[j] + (j-i)*(j-i) for j in range(max(i-3, 0), i))+costs[i-1] # print(f) ...

【Leetcode Daily】2266统计打字方案数

题目浅析想查看原题可以点击题目链接。简单地说，就是给一串打字的按键记录（手机九宫格），请给出这些打字记录可以显现出来的字符串方案个数。思路分享如果只是但看一种数字串的组合方案，就很容易发现这是根据字母个数固定的（3或4）。对每一段连续数字，都可以用 dfs 遍一下。为什么不会因重复超时？因为即使是不同种数字，只要数量相同和字母个数相同，那么组合出的方案也相同。本题最重要的是学到了用 groupby 函数可以把列表中的一段段同种数字整合成一个个值与对应的迭代器，注意，迭代器一旦使用就不可逆，所以要么就使用一次（下面就是只是用了一次量长度），要么就保存到另一个变量使用。代码解答（强烈建议自行解答后再看）参考题解 12345678910111213141516171819202122232425262728293031323334353637383940class Solution: def countTexts(self, pressedKeys: str) -> int: MOD = 10**9 + 7 ...

数据加载中