小蓝在一个 n 行 m 列的方格图中玩一个游戏。开始时,小蓝站在方格图的左上角,即第
时间: 2023-09-18 20:02:16 浏览: 236
n行m列的方格中的第一个格子。小蓝每次可以向右或向下移动一格,直到走到方格图的右下角,即第n行m列的格子。在移动过程中,小蓝要尽可能多地经过方格中的数字,并且不能重复经过同一个格子。小蓝想知道,他最多能够经过多少个数字格子。
解题思路:
这是一个典型的动态规划问题。用dp[i][j]表示小蓝从(1,1)走到(i,j)所经过的最大数字个数。则,小蓝从(i,j)只能从上方和左方两个方向走过来。所以状态转移方程为:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + (方格(i,j)中的数字)
具体的实现算法为:
1. 首先,创建一个大小为n*m的二维数组dp,并将dp每个元素初始化为0。
2. 从左上角开始,依次计算dp[i][j]。
3. 对于第一行和第一列,因为它们只能从上方或左方走过来,所以只需要计算相邻格子的dp值,并加上当前格子中的数字即可。即dp[i][j] = dp[i-1][j] + (方格(i,j)中的数字) 或者 dp[i][j] = dp[i][j-1] + (方格(i,j)中的数字)。
4. 对于其他格子,需要比较从上方和左方走过来的最大dp值,并加上当前格子中的数字。即dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + (方格(i,j)中的数字)。
5. 最后返回dp[n][m]即可得到结果,即小蓝经过的最多数字个数。
例如,对于一个3行4列的方格图:
1 3 5 6
2 8 3 4
6 1 9 2
经过计算得到dp数组为:
1 4 9 15
3 12 15 19
9 13 24 26
dp[3][4]的值为26,即小蓝最多能经过26个数字格子。
阅读全文