AcWing 1015. 摘花生：DP与空间复杂度的优化

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1015. 摘花生：DP与空间复杂度的优化原题链接简单

作者：

aeof , 2020-02-11 11:31:03 , 所有人可见 , 阅读 12456

58

28

题目描述

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

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

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

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

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

输入格式

第一行是一个整数T，代表一共有多少组数据。

接下来是T组数据。

每组数据的第一行是两个整数，分别代表花生苗的行数R和列数 C。

每组数据的接下来R行数据，从北向南依次描述每行花生苗的情况。每行数据有C个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目M。

输出格式

对每组输入数据，输出一行，内容为Hello Kitty能摘到得最多的花生颗数。

样例

输入样例：
2
2 2
1 1
3 4
2 3
2 3 4
1 6 5
输出样例：
8
16

思路

状态表示
集合：定义f[i][j]为从(1, 1)到达(i, j)的所有方案
属性：最大值
状态转移
(i, j)从(i-1, j)即上方过来
(i, j)从(i, j-1)即左方过来
空间压缩
f[i][j]只需要用到这一层和上一层的f元素，所以可以压缩成滚动数组。在此之上，还可以直接压缩成一维数组。

算法1

DP：空间复杂度$O(n^2)$

#include<iostream>
using namespace std;

const int N = 105;
int a[N][N], f[N][N];
int q, row, col;

int main()
{
    cin >> q;
    while(q--){
        cin >> row >> col;
        for(int i = 1; i <= row; i++){
            for(int j = 1; j <= col; j++){
                cin >> a[i][j];
            }
        }

        // f[i][j]指的是到(i, j)的最大花生数
        for(int i = 1; i <= row; i++){
            for(int j = 1; j <= col; j++){
                f[i][j] = max(f[i-1][j], f[i][j-1]) + a[i][j];
            }
        }

        cout << f[row][col] << endl;
    }

    return 0;
}

算法2

DP:滚动数组，空间复杂度$O(n)$

#include<cstring>
#include<iostream>
using namespace std;

const int N = 105;
int a[2][N], f[2][N], q, n, m;

int main()
{
    cin >> q;
    while(q--){
        cin >> n >> m;

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                cin >> a[i&1][j];
                f[i&1][j] = max(f[i&1][j-1], f[(i-1)&1][j]) + a[i&1][j];
            }
        }
        cout << f[n&1][m] << endl;

        memset(f, 0, sizeof f);
    }
}

算法3

DP:空间复杂度$O(n)$

#include<cstring>
#include<iostream>
using namespace std;

const int N = 105;
int a[N][N], f[N], q, n, m;

int main()
{
    cin >> q;
    while(q--){
        cin >> n >> m;

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                cin >> a[i][j];
            }
        }

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                f[j] = max(f[j], f[j-1]) + a[i][j];
            }
        }
        cout << f[m] << endl;

        // 由于多组样例，而二维数组解法由于f[0][...]和f[...][0]都为0，所以没有问题。对于一维数组，上一样例的f数组需要清零，否则影响结果
        memset(f, 0, sizeof f);
    }
}

30 评论

陌上花开Charlie 2022-07-25 16:00

算法3空间复杂度还是$o(n^2)$，应该为:

for(int i = 1;i <= n;++ i)
        for(int j = 1, w;j <= m;++ j)
        {
            cin >> w;
            f[j] = max(f[j], f[j - 1]) + w;
        }

建议作者改一下

Nan97 2021-03-15 19:52

#### 直接倒序输入不香吗

#include <iostream>

using namespace std;

const int N = 110;



int main()
{
    int t;
    cin >> t ;
    while(t -- )
    {
        int row , col ;
        cin >> row >> col;
        int f[N][N] = {0,0};
        //cout << f[0][0] << endl << endl;
        for(int i = 1 ; i <= row ; i ++ )
            for(int j = 1 ; j <= col ; j ++ )
                cin >> f[i][j];

        for(int i = 1 ; i <= row ; i ++ )
            for(int j = 1 ; j <= col ; j ++ )
            f[i][j] += max(f[i - 1][j] , f[i][j - 1]);

        cout << f[row][col] << endl;



    }
}

yueyueyue 2022-02-23 15:57

这个递归时间复杂度更大吧

Nan97 2022-02-24 19:21 回复了 yueyueyue 的评论

哪里有递归呢

魅影 2022-02-26 10:10

这个不是正序输入吗，我也这么写的

Nan97 2022-02-26 18:36 回复了魅影的评论

我忘记了/wul，我也不知道我之前怎么想的了

魅影 2022-02-26 18:44 回复了 Nan97 的评论

哈哈哈时间久远，这个方法和y总方法差不多的，优化过

yueyueyue 2022-02-27 18:05 回复了 Nan97 的评论

不好意思我看成倒序了

acwing_11913 1个月前

为什么优化是从前往后遍历啊？不是用到前一层的数据吗？有没有佬解释一下啊，01背包不是从后往前遍历的吗

爱吸猫的软软 2022-04-02 21:42

这题开个二维数组就行了
#include[HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;
const int N=105;
int dp[N][N];

int main(){
int t;cin>>t;
while(t–){

    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m:j++){
            int num;cin>>num;
            dp[i][j]=max(dp[i][j-1],dp[i-1][j])+num;
        }
    }
    cout<<dp[n][m]<<endl;

}



return 0;

}

Format 9个月前

为什么都喜欢开静态数组呢？
#include [HTML_REMOVED]
#include [HTML_REMOVED]
using namespace std;
const int N=105;
int main(){
int t;
cin>>t;
while(t–){
int c,r;
cin>>r>>c;
vector[HTML_REMOVED]> a(r+1,vector[HTML_REMOVED](c+1,0));
for(int i=1;i<=r;i){
for(int j=1;j<=c;j){
cin>>a[i][j];
a[i][j]=max(a[i-1][j]+a[i][j],a[i][j-1]+a[i][j]);
}
}
cout<<a[r][c]<<endl;
}
}

做完这题就回老家结婚 2022-07-25 11:57

算法3空间复杂度还是$o(n^2)$的

Althemeta 2022-03-09 19:27

贪心$O(n)$

包子云 2022-03-06 15:58

边输入边计算（我也不知道为什么可以，虽然代码短了些但是运行时间多了几十ms）

#include<cstring>
#include<iostream>
using namespace std;

const int N = 105;
int a[N][N], f[N], q, n, m;

int main()
{
    cin >> q;
    while (q--) {
        cin >> n >> m;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> a[i][j];
                f[j] = max(f[j], f[j - 1]) + a[i][j];

            }
        }


        cout << f[m] << endl;

        // 由于多组样例，而二维数组解法由于f[0][...]和f[...][0]都为0，所以没有问题。对于一维数组，上一样例的f数组需要清零，否则影响结果
        memset(f, 0, sizeof f);
    }
}