愿此后再无WA 2022-02-19 13:17 采纳率: 94.1%
浏览 93
已结题

想问问以下两种动态规划方法有什么不同?为什么会导致结果不一样?

img


第一种做法的思路是先不断递归求出下格子与右格子拿到的金币数,然后根据两者的最大值来判断是走下方还是走右方。期间使用了标记数组剪枝

def dfs(x,y):
    if x > n-1 or y > n-1:
        return 0
    if x == n-1 and y == n-1:
        return nums[x][y]
    if not used[x][y]:
        used[x][y] = max(dfs(x+1,y),dfs(x,y+1)) + nums[x][y]
    return used[x][y]
    
    
n = int(input())
nums = []
for i in range(n):
    nums.append(list(map(int,input().split())))
    
used = [[0 for i in range(n)] for j in range(n)]
print(dfs(0,0))

第二种思路是要想走到这个位置,就要看这个位置的上方拿的金币多点还是左方拿的金币多点,哪边拿得多就从哪边走过来

nums = []
n = int(input())
for i in range(n):
    nums.append(list(map(int, input().split())))
 
dp = [[0 for i in range(n)] for j in range(n)]

dp[0][0] = nums[0][0]
for i in range(1, n):
    dp[i][0] = dp[i - 1][0] + nums[i][0]
    dp[0][i] = dp[0][i - 1] + nums[0][i]

for i in range(1, n):
    for j in range(1, n):
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + nums[i][j]
 
print(dp[n - 1][n - 1])

一种做法能拿满分,另一种做法只能拿30分,没有出现运行超时的情况,都是解答错误.

  • 写回答

1条回答 默认 最新

  • 爱在凌晨 2022-02-23 09:46
    关注

    看着应该没问题,递归的话,n 如果大一点话,可能会栈溢出, 不知道这种情况是不是也是解答错误

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 3月4日
  • 已采纳回答 2月24日
  • 修改了问题 2月19日
  • 创建了问题 2月19日

悬赏问题

  • ¥15 STM32——硬件IIC从机通信代码实现
  • ¥15 关于GRSL投稿的疑问
  • ¥15 微生物组数据分析--微生物代谢物
  • ¥30 求一跃动小子保卫主公Java算法实现
  • ¥15 地图软件开发技术答疑(api, 地点获取,外观样式)
  • ¥20 物理远程控制麦克风使用问题
  • ¥15 打印预览会泄漏纸钱包密码吗
  • ¥15 在hololens1上运行unity项目只有空窗口
  • ¥25 TABLEAU PREP无法打开
  • ¥15 百度帐号问题/centos