题目描述

Hello Kitty想摘点花生送给她喜欢的米老鼠。

她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。

地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。

Hello Kitty只能向东或向南走，不能向西或向北走。

问Hello Kitty最多能够摘到多少颗花生。

思路

正推

每一位只能走右边或者下面，
所以，状态转移方程如下。

$f[i][j] = max ( f[i - 1][j] , f[i][j - 1] ) + g[i][j]$

反推

最后一位只能由上一位走的得到，而上一位只能从上或左得到。
所以，状态转移方程如下。

$f[i][j] = max ( f[i + 1][j] , f[i][j + 1] ) + g[i][j]$

反推

(DP) $O(nm)$

C++ 代码

#include <bits/stdc++.h>

using namespace std ;

const int N = 1e2 + 5 ;

int n ; 

int main ( ) {

    cin >> n ; 
    while ( n -- ) {

        int x , y ;
        cin >> x >> y ;

        int g[N][N] ;
        for ( int i = 1 ; i <= x ; i ++ )
            for ( int j = 1 ; j <= y ; j ++ )
                cin >> g[i][j] ;

        int f[N][N] = { 0 } ;
        for ( int i = x ; i >= 1 ; i -- ) 
            for ( int j = y ; j >= 1 ; j -- ) 
                f[i][j] = max ( f[i + 1][j] , f[i][j + 1] ) + g[i][j] ;

        cout << f[1][1] << endl ;

    }

    return 0 ;

}

正推

(DP) $O(nm)$

C++ 代码

#include <bits/stdc++.h>

using namespace std ;

const int N = 1e2 + 5 ;

int n ; 

int main ( ) {

    cin >> n ; 
    while ( n -- ) {

        int x , y ;
        cin >> x >> y ;

        int g[N][N] ;
        for ( int i = 1 ; i <= x ; i ++ )
            for ( int j = 1 ; j <= y ; j ++ )
                cin >> g[i][j] ;

        int f[N][N] = { 0 } ;
        f[1][1] = g[1][1] ;
        for ( int i = 1 ; i <= x ; i ++ ) 
            for ( int j = 1 ; j <= y ; j ++ ) 
                f[i][j] = max ( f[i - 1][j] , f[i][j - 1] ) + g[i][j] ;

        cout << f[x][y] << endl ;

    }

    return 0 ;

}