有一个N行N列的网格，左上角是起点，右下角是终点，每个格子上都有价值不同的礼物，用格子中的数字表示礼物的价值。经过该格子即可获得该礼物。每次行走只能往右走或往下走，那么最终能得到礼物的总价值最大是多少？起点和终点也有数字，从起点出发、到达终点，能获得起点和终点上的礼物。 输入描述： 输入第一行为一个正整数N，2≤N≤20，表示网格的大小。接下来有N行，每行有N个正整数，用空格隔开。 输出描述： 输出一个正整数，表示能得到礼物的总价值的最大值，答案不超出int型的范围。

这是一个典型的动态规划问题，可以采用状态转移方程来解决。

定义状态 $f(i,j)$ 表示从起点到 $(i,j)$ 格子能够获得的最大礼物价值，那么状态转移方程为：

$$f(i,j) = max\{f(i-1,j),f(i,j-1)\} + grid(i,j)$$

其中 $grid(i,j)$ 表示 $(i,j)$ 格子上的礼物价值。因为只能向右或向下走，所以到达 $(i,j)$ 格子的路径只能从 $(i-1,j)$ 或 $(i,j-1)$ 转移过来，因此 $f(i,j)$ 的值只能由这两个状态转移而来，取其中的较大值再加上当前格子上的礼物价值即为到达当前格子能够获得的最大礼物价值。

最终的答案即为 $f(N,N)$。时间复杂度为 $O(N^2)$。

以下是Python代码实现：

相关问题

在C语言中：有一个N行N列的网格，左上角是起点，右下角是终点，每个格子上都有价值不同的礼物，用格子中的数字表示礼物的价值。经过该格子即可获得该礼物。每次行走只能往右走或往下走，那么最终能得到礼物的总价值最大是多少？起点和终点也有数字，从起点出发、到达终点，能获得起点和终点上的礼物。 输入描述： 输入第一行为一个正整数N，2≤N≤20，表示网格的大小。接下来有N行，每行有N个正整数，用空格隔开。

这是一个经典的动态规划问题，可以使用动态规划来解决。

设 $dp[i][j]$ 表示从起点到达第 $i$ 行第 $j$ 列的格子时能获得的最大价值。则有以下状态转移方程：

$$dp[i][j] = \max(dp[i-1][j], dp[i][j-1]) + grid[i][j]$$

其中 $grid[i][j]$ 表示第 $i$ 行第 $j$ 列的格子上的礼物价值。

初值为 $dp[1][1] = grid[1][1]$，因为从起点到起点的最大价值就是起点上的礼物价值。

最终的答案即为 $dp[N][N]$，表示从起点到终点时能获得的最大价值。

下面是 C 语言的代码实现：

#include <stdio.h>

#define MAXN 20

int grid[MAXN+1][MAXN+1];
int dp[MAXN+1][MAXN+1];

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int n;
    scanf("%d", &n);

    // 读入礼物价值
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &grid[i][j]);
        }
    }

    // 动态规划
    dp[1][1] = grid[1][1];
    for (int i = 2; i <= n; i++) {
        dp[i][1] = dp[i-1][1] + grid[i][1];
        dp[1][i] = dp[1][i-1] + grid[1][i];
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= n; j++) {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }

    // 输出结果
    printf("%d\n", dp[n][n]);

    return 0;
}

给定m行和n列网格，有一个机器人从左上角(0,0)出发，每一步可以向下或向右走一步，问多少种不同的方式走到右下角？

这是一道经典的动态规划问题。我们可以定义一个二维数组 $dp$，其中 $dp[i][j]$ 表示从 $(0,0)$ 出发到达 $(i,j)$ 的不同路径数目。

根据题目要求，机器人只能向下或向右走，因此对于任意一个格子 $(i,j)$，它只能从上方格子 $(i-1,j)$ 或左方格子 $(i,j-1)$ 走过来，因此有：

$$dp[i][j] = dp[i-1][j] + dp[i][j-1]$$

初始条件为 $dp[0][0]=1$，即起点只有一种到达方式。

最终答案为 $dp[m-1][n-1]$，即从起点到终点的不同路径数目。

以下是Python代码实现：

def uniquePaths(m: int, n: int) -> int:
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1
    for i in range(m):
        for j in range(n):
            if i > 0:
                dp[i][j] += dp[i-1][j]
            if j > 0:
                dp[i][j] += dp[i][j-1]
    return dp[m-1][n-1]

时间复杂度为 $O(mn)$，空间复杂度为 $O(mn)$。