第一种做法的思路是先不断递归求出下格子与右格子拿到的金币数,然后根据两者的最大值来判断是走下方还是走右方。期间使用了标记数组剪枝
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分,没有出现运行超时的情况,都是解答错误.