小记

写采药的时候提交了一下代码没有过

检查半天也没检查出来什么问题
看了一下题解才发现忽略了一个细节上的问题

下面看下有bug的代码

// m 表示有多少个药草 w和v分别表示药草的采摘时间和价值
for (int i = 1;i <= m;i ++ ){
    cin >> w >> v; 
    for (int j = n;j >= w;j -- ){
        dp[i][j] = max (dp[i- 1][j], dp[i - 1][j - w] + v);
    }
}

再看下这种写法的正确形式

for (int i = 1;i <= m;i ++ ){
    cin >> w >> v; 
    for (int j = n;j > 0;j -- ){
        dp[i][j] = dp[i - 1][j]; // 先继承一下
        if(j >= w)
            dp[i][j] = max (dp[i- 1][j], dp[i - 1][j - w] + v);
    }
}

这边多了一个继承上一次的结果，并且在j < w的时候依然继承是因为要防止在 j < w的时候可以选到i- 1之前的药草

可能说的不是很清楚，可以好好体会一下

一维数组实现

可以发现每次dp都只是利用前一次的结果，对于前前…次的根本用不到
所以利用滚动数组的思想直接用一维数组就行了

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