🎁 迎长周末 & 六一,VIP通行证6个月立减$50,蓝莓立减$25 🎁
<
查看: 672| 回复: 5
收起左侧

[动态规划] 求帮忙找bug: 64. Minimum Path Sum。 感谢🙏

Yyhhhi | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   47
87%
13%
7

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x

知道DP可以写,想用DFS+memo写一下,但是缺找不出bug,请大家帮忙看一眼

class Solution:

    def minPathSum(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]:
            return 0

        return self.traverse(grid, 0, 0, {})

    def traverse(self, grid, i, j, memo):
        if i >= len(grid) or j >= len(grid[0]):
            return
        
        if (i, j) in memo:
            return memo[(i, j)]
        
        right = self.traverse(grid, i, j + 1, memo)
        down = self.traverse(grid, i + 1, j, memo)

        if right and down:
            value = min(right, down) + grid[i][j]
        elif right:
            value = right + grid[i][j]
        elif down:
            value = down + grid[i][j]
        else:
            value = grid[i][j]

        memo[(i, j)] = value
        return value

上一篇:leetcode现在block简单的script access了?
下一篇:求问大神们:Meta tag的题如何去 prioritize?
 楼主| Yyhhhi 2024-3-9 03:19:22 | 显示全部楼层
本楼:   👍  1
100%
0%
0   👎
全局:   47
87%
13%
7
walkby55 发表于 2024-3-7 18:06
这里最好是return -1或者是一个代表异常的integer,虽然python不强制要求return的类型是一致的但是best pra ...

太感谢你了!!!!多谢多谢,以后会多注意return value
回复

使用道具 举报

 楼主| Yyhhhi 2024-3-8 04:38:43 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   47
87%
13%
7
截个图,好看一些
image.png
回复

使用道具 举报

本楼:   👍  0
0%
0%
0   👎
全局:   321
98%
2%
7
traverse 里第二行,应该return None?
回复

使用道具 举报

 楼主| Yyhhhi 2024-3-8 08:55:55 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   47
87%
13%
7
xixixixixix 发表于 2024-3-7 14:38
traverse 里第二行,应该return None?

return 跟 return None是一样的吧。试了一下,一样的错 :(
回复

使用道具 举报

walkby55 2024-3-8 10:06:30 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   8
100%
0%
0
本帖最后由 walkby55 于 2024-3-7 16:10 编辑
  1. def traverse(self, grid, i, j, memo):
  2.         if i >= len(grid) or j >= len(grid[0]):
  3.             return
复制代码
这里最好是return -1或者是一个代表异常的integer,虽然python不强制要求return的类型是一致的但是best practice最好还是能保证每个return branch都是相同的类型。
  1. if right and down:
  2.     value = min(right, down) + grid[i][j]
  3. elif right:
  4.     value = right + grid[i][j]
  5. elif down:
  6.     value = down + grid[i][j]
  7. else:
  8.     value = grid[i][j]
复制代码
错误点在这里
  1. if right and down:
复制代码
,如果你仔细看failed的test case就会发现grid里是有0的,而right 或者 down 为0时这里的判断就会出现问题,按照你的写法最好是能写成
  1. if right is not None and down is not None:
复制代码
,后几个elif同理
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

Advertisement
>
快速回复 返回顶部 返回列表