本文介绍: 定义一个二维数组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）
有一个n行m列的矩阵，每个格子中有一个正整数。现在要从左上角的格子(1, 1)出发，每次只能向下或向右走一格，最后到达右下角的格子(n, m)。在走过的格子中取数，求取得的数的和的最大值。
思路： 考虑动态规划的方法解决这个问题。定义一个二维数组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]即为所求的结果。
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
