有一个n行m列的矩阵，每个格子中有一个正整数。现在要从左上角的格子(1, 1)出发，每次只能向下或向右走一格，最后到达右下角的格子(n, m)。在走过的格子中取数，求取得的数的和的最大值。
输入： 第一行包含两个整数n和m，表示矩阵的行数和列数。 接下来n行，每行包含m个整数，表示每个格子中的数。
输出： 输出一个整数，表示取得的数的和的最大值。
输入示例： 3 3 1 2 3 4 5 6 7 8 9
输出示例： 29
思路： 考虑动态规划的方法解决这个问题。定义一个二维数组dp，其中dp[i][j]表示从(1,1)到(i,j)的路径中取得的数的和的最大值。则有如下状态转移方程： dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + matrix[i][j] （i>1，j>1） dp[i][j] = dp[i-1][j] + matrix[i][j] （i>1，j=1） dp[i][j] = dp[i][j-1] + matrix[i][j] （i=1，j>1） dp[i][j] = matrix[i][j] （i=1，j=1）
根据状态转移方程，可以从左上角开始逐行逐列计算dp数组的值，最终dp[n][m]即为所求的结果。
原文地址:https://blog.csdn.net/SYC20110120/article/details/136045735
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_68283.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
