问题描述
有一个N x N的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。
你站在最左上角的格子里,每次可以从一个格子走到它右边或下边的格子里。
请问如何走才能拿到最多的金币。
输入格式
第一行输入一个正整数n。
以下n行描述该方格。金币数保证是不超过1000的正整数。
输出格式
最多能拿金币数量。
样例输入
3
1 3 3
2 2 2
3 1 2
样例输出
11
数据规模和约定
n<=1000
自己的一些笔记：
动态规划DP： 确定二维数组大小为n*n，将金币数字存入nums[n][n]。观察题目，可以建立二维数组
存储累加最大金币数目，称为dp[i][j]，其中i、j表示当前所在格子的行和列。
1、确定初始范围：从左上角开始走，规定只能往右边或者下面走，确定最左上角为初始值，
令dp[0][0] = nums[0][0]；
如下图所示，可以一层一层往里面深入，dp存储最大金币路径。首先是最外层的最左边的一列，
因为不能往左边走，因此如果出现在最左边的一列，那一定是径直往下走的，而不是先走到了右边又拐回来的，
因此可以用dp[i][0] = dp[i - 1][0] + nums[i][0]表示最左边的一列的状态值，
当前状态等于上一个状态（前面的路径上所有金币之和）加现在格子里的金币数。
同样地，最上面一行也是如此，因为走到最上面的格子里也只能横着走，因此用
dp[0][i] = dp[0][i - 1] + nums[0][i]表示最上面一行当前状态的金币之和
（最大金币数——只有一条路，也不得不最大）。
2、状态转移函数：写状态转移函数，就是找从一个阶段向另一个阶段过度的具体形式,
描述的是两个相邻子问题之间的关系(递推式)。
例如黄格子A，A可由B和C走过来，要求最大的金币数量之和，就看B和C哪个存储的“路径金币之和”最大，
（dp的每个格子存储的是当前路径金币之和最大值），B和C都是存储的走到该格路径金币最大的数值，
现在要求A，就看B和C哪个大，哪个大就加上A的金币数目作为到A点的路径金币之和最大值。
因此i和ji都从1开始，用dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + nums[i][j]表示
最优子结构，表示当前路径金币之和最大值。
上述示意图看蓝桥杯收藏夹对应CSDN
'''
# 我的代码：
n=int(input())
nums=[[list(map(int,input().split()))]for i in range(n)] # 这样更好
dp=[[0 for i in range(n)]for j in range(n)] # 注意本题dp[][]定义格式
dp[0][0]=nums[0][0] # 赋初始值
for i in range(n):
for j in range(n):
if i==0:
dp[0][i]=dp[0][i-1]+nums[0][i]
elif j==0:
dp[j][0]=dp[j-1][0]+nums[i][0]
else:
dp[i][j]=max(dp[i-1][j],dp[i][j-1])+nums[i][j]
print("{:.d}".format(dp[n-1][n-1]))
'''
# 正确代码：
n = int(input()) # 确定矩阵大小
a = [[] for i in range(n)] # 创建空矩阵
for i in range(n): # 金币初始化
a[i] = list(map(int, input().split()))
for i in range(n): # 拿金币三种处理
for j in range(n):
if i == 0 and j == 0:
a[i][j] = a[i][j]
elif i == 0:
a[i][j] = a[i][j - 1] + a[i][j]
elif j == 0:
a[i][j] = a[i - 1][j] + a[i][j]
else:
a[i][j] = a[i][j] + max(a[i - 1][j], a[i][j - 1])
print(a[n - 1][n - 1])
