在C语言中:有一个N行N列的网格,左上角是起点,右下角是终点,每个格子上都有价值不同的礼物,用格子中的数字表示礼物的价值。经过该格子即可获得该礼物。每次行走只能往右走或往下走,那么最终能得到礼物的总价值最大是多少?起点和终点也有数字,从起点出发、到达终点,能获得起点和终点上的礼物。 输入描述: 输入第一行为一个正整数N,2≤N≤20,表示网格的大小。接下来有N行,每行有N个正整数,用空格隔开。
时间: 2023-11-11 20:04:55 浏览: 63
这是一个经典的动态规划问题,可以使用动态规划来解决。
设 $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 语言的代码实现:
```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;
}
```
相关推荐
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)