|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 糖逗 于 2020-5-8 18:11 编辑
题目描述:
- 在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?
-  
- 示例 1:
- 输入:
- [
-   [1,3,1],
-   [1,5,1],
-   [4,2,1]
- ]
- 输出: 12
- 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
-  
- 提示:
- 0 < grid.length <= 200
- 0 < grid[0].length <= 200
- 来源:力扣(LeetCode)
- 链接:https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof
- 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码
- #include <iostream>
- #include <vector>
- using namespace std;
- int solution(vector<vector<int> >& input){
- if(input.size() == 0 || input.size()==1 && input[0].size() == 0) return 0;
- int row = input.size();
- int col = input[0].size();
- int dp[row][col];
- dp[0][0] = input[0][0];
- for(int i = 1; i < row; i++){
- dp[i][0] = input[i][0] + dp[i-1][0];
- }
- for(int j = 1; j < col; j++){
- dp[0][j] = input[0][j] + dp[0][j-1];
- }
- for(int i = 1; i < row; i++){
- for(int j = 1; j < col; j++){
- dp[i][j] = input[i][j] + max(dp[i-1][j], dp[i][j-1]);
- }
- }
- return dp[row-1][col-1];
- }
- int main(void){
- vector<vector<int> > input;
- cout << "please send row" << endl;
- int row;
- cin >> row;
- cin.clear();
- input.resize(row);
- cout << "please send coloumns" << endl;
- int col;
- cin >> col;
- cin.clear();
- cout << "please send number for the matrix" << endl;
- int number;
- for(int i = 0; i < row; i++){
- for(int j = 0; j < col; j++){
- cin >> number;
- input[i].push_back(number);
- }
- }
-
- int res = solution(input);
- cout << res << endl;
- return 0;
- }
复制代码
注意事项:
1.暂无。
|
|