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

Question

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

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分，没有出现运行超时的情况，都是解答错误.

Answer 1

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