51Nod 1083 矩阵取数问题

发表于 | 分类于 | 阅读次数: |
字数统计: 438 | 阅读时长 ≈ 2

1083 矩阵取数问题

基准时间限制：1 秒 空间限制：131072 KB 分值: 5 难度：1级算法题 收藏 关注

描述

一个N/N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，从左上走到右下，只能向下向右走，求能够获得的最大价值。
例如：3 / 3的方格。
1 3 3
2 1 3
2 2 1
能够获得的最大价值为：11。

Input

第1行：N，N为矩阵的大小。(2 <= N <= 500)
第2 - N + 1行：每行N个数，中间用空格隔开，对应格子中奖励的价值。（1 <= N[i] <= 10000)

Output

输出能够获得的最大价值。

Input示例

3
1 3 3
2 1 3
2 2 1

Output示例

11

题解

动态规划入门题，输入的 dp[][] 二维数组矩阵，用 dp[i][j] 表示从起点到第 x 行，第 y 列的最优路径上的数之和，而最优路径为 dp[i][j] 的值加上来自其上方或左方的值中的较大的一个值，累计到最后则为最大的值，所以状态转移方程为
dp[i][j] = dp[i][j] + max(dp[i-1][j] , dp[i][j-1])
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <utility>
#define ll long long

using namespace std ;

ll dp[505][505] ;

int main(){
    ll n ;
    cin >> n ;
    for ( int i = 1 ; i <= n ; i ++ ){
        for ( int j = 1 ; j <= n ; j ++ ){
            cin >> dp[i][j] ;
        }
    }
    for ( int i = 1 ; i <= n ; i ++ ){
        for ( int j = 1 ; j <= n ; j ++ ){
            dp[i][j]= max(dp[i-1][j] , dp[i][j-1]) + dp[i][j] ;
        }
    }
    cout << dp[n][n] << endl ;
    return 0 ;
}