本文主要是介绍拿礼物，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
在一个 m*n 的棋盘中的每一个格都放一个礼物，每个礼物都有一定的价值（价值大于0）.你可以从棋盘的左下角开始拿各种里的礼物，并每次向左或者向下移动一格，直到到达棋盘的右上角。给定一个棋盘及上面个的礼物，请计算你最多能拿走多少价值的礼物？
递归
动态规划
#include <stdio.h>#define MAXRAW 24int g_raw = 0;
int g_col = 0;
int g_max = 0;
int g_curr = 0;
int g_matrix[MAXRAW][MAXRAW] = {{0}};void InitMaxAndCurr()
{g_max = 0;g_curr = 0;
}void GetInputMatrix()
{scanf("%d%d", &g_raw, &g_col);for (int m = 0; m < g_raw; m++) {for (int n = 0; n < g_col; n++) {scanf("%d", &g_matrix[m][n]);}}
}void LookMax(int m, int n)
{if (m == 0 && n == (g_col - 1)) {g_max = g_max > g_curr ? g_max : g_curr;return;}if (m > 0) {g_curr += g_matrix[m - 1][n];LookMax(m - 1, n);g_curr -= g_matrix[m - 1][n];}if (n < g_col - 1) {g_curr += g_matrix[m][n + 1];LookMax(m, n + 1);g_curr -= g_matrix[m][n + 1];}
}int main()
{InitMaxAndCurr();GetInputMatrix();// 递归g_curr = g_matrix[g_raw - 1][0];LookMax(g_raw - 1, 0);printf("%d\n", g_max);// 动态规划int dp[MAXRAW][MAXRAW] = {{0}};int left;int down;dp[g_raw - 1][0] = g_matrix[g_raw - 1][0];for (int i = g_raw - 2; i >= 0; --i) {dp[i][0] = g_matrix[i][0] + dp[i + 1][0];}for (int j = 1; j <= g_col - 1; ++j) {dp[g_raw - 1][j] = g_matrix[g_raw - 1][j] + dp[g_raw - 1][j - 1];}for (int i = g_raw - 2; i >= 0; i--) {for (int j = 1; j <= g_col - 1; j++) {dp[i][j] = (dp[i + 1][j] > dp[i][j - 1] ? dp[i + 1][j] : dp[i][j - 1]) + g_matrix[i][j];}}printf("%d", dp[0][g_col - 1]);return 0;
}
这篇关于拿礼物的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
