鱼C论坛

 找回密码
 立即注册
查看: 2018|回复: 0

[技术交流] C++刷剑指offer(面试题47. 礼物的最大价值)【动态规划】

[复制链接]
发表于 2020-3-31 17:04:03 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 糖逗 于 2020-5-8 18:11 编辑

题目描述:
  1. 在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?

  2.  

  3. 示例 1:

  4. 输入:
  5. [
  6.   [1,3,1],
  7.   [1,5,1],
  8.   [4,2,1]
  9. ]
  10. 输出: 12
  11. 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
  12.  

  13. 提示:

  14. 0 < grid.length <= 200
  15. 0 < grid[0].length <= 200

  16. 来源:力扣(LeetCode)
  17. 链接:https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof
  18. 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码


  1. #include <iostream>
  2. #include <vector>

  3. using namespace std;

  4. int solution(vector<vector<int> >& input){
  5.         if(input.size() == 0 || input.size()==1 && input[0].size() == 0) return 0;
  6.         int row = input.size();
  7.         int col = input[0].size();
  8.         int dp[row][col];
  9.         dp[0][0] = input[0][0];
  10.         for(int i = 1; i < row; i++){
  11.                 dp[i][0] = input[i][0] + dp[i-1][0];
  12.         }
  13.         for(int j = 1; j < col; j++){
  14.                 dp[0][j] = input[0][j] + dp[0][j-1];
  15.         }
  16.         for(int i = 1; i < row; i++){
  17.                 for(int j = 1; j < col; j++){
  18.                         dp[i][j] = input[i][j] + max(dp[i-1][j],  dp[i][j-1]);
  19.                 }
  20.         }
  21.         return dp[row-1][col-1];
  22. }

  23. int main(void){
  24.         vector<vector<int> > input;
  25.         cout << "please send row" << endl;
  26.         int row;
  27.         cin >> row;
  28.         cin.clear();
  29.         input.resize(row);
  30.         cout << "please send coloumns" << endl;
  31.         int col;
  32.         cin >> col;
  33.         cin.clear();
  34.         cout << "please send number for the matrix" << endl;
  35.         int number;

  36.         for(int i = 0; i < row; i++){
  37.                 for(int j = 0; j < col; j++){
  38.                         cin >> number;
  39.                         input[i].push_back(number);
  40.                 }
  41.         }       
  42.        

  43.         int res = solution(input);
  44.         cout << res << endl;
  45.         return 0;
  46. }
复制代码



注意事项:
1.暂无。

本帖被以下淘专辑推荐:

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-3 12:24

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表