题目描述

其实朴素做法只需要初始化f[0][0]=1这种情况就好了，因为在计算后面的情况时，f[i][0]都会因为体积不够导致只能从f[i-1][0]这种状态转移过来，即f[i][0]=f[i-1][0]

大佬总结的非常到位！！！

tql

确实，内循环从 0 开始就可以只初始化 f[0][0] = 1。

妙啊

我竟然懂了

我是ikun你记住

我才是ikun

你这个假粉你根本不了解它

逆天了，孩子，你无敌了

f[i][j] = f[i - 1][j] + f[i][j - i]，为啥能变成f[j]=f[j]+f[j-1]那前面一个是[i-1]一个是[i]为啥能去掉

我建议你画两行数组，第一行表示$i-1$的dp结果，第二行表示$i$的dp结果。
比如，压缩之前是：$ f[i][j] = f[i - 1][j] + f[i][j - i] $这样，$(i,j)$的结果和上一行$j$相同位置有关，也和$(i, j-1)$即当前行有关。

每次开始$j$循环的时候，一维数组$dp$里放的其实是dp[i-1][j]的值了，这里$ f[i][j] = f[i - 1][j] + f[i][j - i] $里面的$f[i-1][j]$其实就是上一次更新结果，而$f[i][j-i]$因为是$i$，所以是当前行的更新结果，而更新$j$需要用到$j-i$比$j$小，所以需要从小到大更新。

懂了

而求方案数时，当都不选时，方案数是 1（即前 i 个物品都不选的情况也是一种方案），所以需要初始化为 1
为啥都不选是一种方案欸，都不选的话不就是0嘛

都不选指的是数的本身吧

同蒙

其实只需要更新f[0][0]=1也行，但是需要下方第二层循环for (int j=1;j<=n;j++)需要j从0开始循环
具体原因是i=1开始循环，j第一次大于等于i时，就会调用f[i][0]，而f[i][0]本身之前会调用f[i-1][0]，即f[0][0]
需要注意的是，这个时候必须初始化f[0][0]，才会让第一次选i的f[i][j-i]方案不为0

结合下面的f[i][0] = 1;来看的话 他初始化为1应该是基于容量为0时，此时前 i 个物品全不选也是一种方案

这个是正确的
y总在完全背包做法中表明f[i][j]，表示的是从1到i（体积为1到i，数量为无限个）中选，总体积恰好为j，的所有选法的集合。
所以 f[0] 是由 f[1~i][0] 简化（即去掉前面一维）后得到，表明总体积为0的时候所有选法的数量，自然为 1 .

最朴素版本也AC了，是数据有点弱么

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

const int N = 1010, mod = 1e9 + 7;
int f[N][N];
int n;

int main()
{
    cin >> n;

    for(int i = 0; i <= n; i ++ )   f[i][0] = 1;

    for(int i = 1; i <= n; i ++ )
        for(int j = 0; j <= n; j ++ )
        {
            f[i][j] = f[i - 1][j] % mod; 
            for(int k = 1; k * i <= j; k ++ )
                f[i][j] = (f[i][j] + f[i - 1][j - k * i]) % mod;
        }

    cout << f[n][n] << endl;
    return 0;
}

和我的想法一样，y总的那个自己想实在太难想了，但是这个结合背包问题挺好想的

把f[i][j] = f[i - 1][j] % mod; 这句去掉然后k从0开始循环也能AC

#include<iostream>
using namespace std;

const int N=1010, mod=1e9+7;
int f[N][N];

int main()
{
    int n;
    cin>>n;

    //不能反过来初始化f[0][i]，表示从0这个数中选，要选到达到i，显然无解
    for(int i=0;i<=n;i++) f[i][0]=1;

    //原始模板，会tle
    for(int i=1;i<=n;i++)
        for(int j=0;j<=n;j++)
            for(int k=0;j>=k*i;k++)
                f[i][j]=(f[i][j]+f[i-1][j-k*i])%mod;

    cout<<f[n][n]<<endl;

    return 0;
}

按你说的，为啥我错了

错误的

因为这里是计数型dp，不是max，把f[i][j]放到循环里面会多累加一次，max(本身，本身) = 本身，本身 + 本身 = 两倍本身了

f[i][j] = f[i - 1][j] % mod; // 特殊 f[0][0] = 1
请问这个语句是什么作用？

就是本次循环之前j<i，自然不能调入f[i][j-i]

请问一下朴素做法到变形做法那里，为什么状态转移方程里面有i - 1还能够直接把第一维去掉啊，而且这种问题在第一次循环也就是i = j = 1的时候f[1] = (f[1] + f[0]) % mod，但是f[1]不知道啊，怎么求出来的，头晕

这就是完全背包啊

现在搞明白了，谢谢回复

不用谢

老哥，能详细说一下吗? 我突然有点懵了

你是那里不清楚呀，如果是去掉第一维的话就是之前背包讲的滚动数组优化了，具体的可以去博客园搜一下，如果是我说的f[1]不知道的话是因为我之前忽视了f数组定义在主函数外面所以f[1]已经初始化为0了

我是f[1]的值那里不太懂，全局数组初始化为0，现在get了!

okk

请问一下“为什么状态转移方程里面有i - 1还能够直接把第一维去掉啊”怎么思考解决的😳

额这个就是滚动数组的一个应用，就是如果所有的状态转移里面只涉及到i和i - 1的话就能去掉，具体的可以去看看这个博客https://www.cnblogs.com/kimsimple/p/6883871.html

谢谢谢~

看成完全背包问题就好做了

这个集合划分的过程不是很能理解。

### 感谢

有一个问题既然这个是完全背包变形，那真正的计数类dp应该是什么？
楼主可否给出一道例题？

我认为计数类dp 指的是取count而不是取max的意思吧

所以这题是道很好的计数类dp

感谢count

初值问题那里，方案数初始化为1是因为一个数可以划分为它自身和0，所以它自身就是一种方案。这样解释可能更好理解一点

你说的这种情况应该是当i=j时，选一个i时的方案

get√

大佬，朴素写法，第二层循环j为什么下标要从0开始

可以回顾一下完全背包的内容，搞懂01和完全的区别

完全背包的j循环其实是可以从1开始的呀, 因为背包体积为0的时候, 价值肯定为0(假设没有vi=0的物品)
j=0是需要计算的, 当j为0的时候 f[i][j]=1. 如果初始化只是把f[0][0]=0, 那循环肯定要从0开始
楼主这里把f(1-n,j)都初始化为1了, 其实这里j是可以从1开始的

哈哈哈谢谢，现在已经悟了

f[ 0 ][ 0 ] 代表的是前0个物品 (数字) 选出体积 (和) 为0的方案， i 取不到 0，f[ 0 ][ 0 ] 不是非法状态吗？ 况且题目要求 n >= 1 , 初始化的起点应该是 f [ 1 ][ 0 ] 才对啊？从集合含义去考虑， f [ 0 ] [ 0 ] 不合法呀。

i 可以取 0 呀，0 个物品都不选可以拼成 0 所以方案是 1。 初始起点 f[0][0] 是因为在计算状态的时候要用到这个f[0][0]

我f[0][0] 随便设初值也ac了

朴素枚举j的时候 没有必要从 0 开始

其实都一样，就看自己的边界怎么处理了，都是正确的

#include <iostream>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int f[N][N];
int main()
{
    int n; cin >> n;
    for(int i = 1; i <= n; i++) f[1][i] = 1;

    for (int i = 2; i <= n; i ++) {
        for (int j = 1; j <= n; j ++) {
            f[i][j] = f[i - 1][j] % mod;
            if (j > i) f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod;
            if(i == j) f[i][j] += 1;
        }
    }

    cout << f[n][n] << endl;
}

不知道这样行不行🤣🤣我也不理解边界为0的时候

这题解太牛逼了，谢谢！！！

为什么后面那里是 f [ j ] = ( f [ j ] + f [ j - i ] ) % mod ？为什么括号里面需要加起来呀？

为什么要 %mod ? 不太懂这个地方

爱了爱了犹如拨开云层见天明的感觉

6