闫氏dp法学习

目录

闫式dp分析法模板：

例1：01背包

例2：完全背包问题

例3：石子合并（区间dp）

例4：最长公共子序列

例5：整数划分（计数类dp）

例6：计数问题（数位统计dp）

例7：蒙德里安的梦想（状态压缩dp）

例8：砝码称重（背包问题）

例9：滑雪（记忆化搜索）

---

学习来源：b站闫式dp分析法以及一些acwing的dp问题视频讲解；

导言：遇到dp问题，常常无从下手，往往是干瞪眼；y总用解决两数相乘的例子形象的说明了闫式dp分析法对dp问题解决的帮助：算出324*728，我们可以用小学老师讲的列竖式，一步一步算出来，但是让我们直接口算，可能就干瞪眼了；dp问题也是，有了闫式dp分析法，我们可以对dp问题有个明确的解题方向和模板，帮助解决和理解dp问题；

闫式dp分析法模板：

对我而言，想出状态表示这一步可能比较绕，这一点只能通过多做题，多积累，之前做过类似的，才可以类比的用dp数组表示当前问题的状态；

状态表示：化零为整，意思就是把这些独立枚举的方案分成类别，零散的给它整成一类，dp的优化就在于此，暴力的解法是把所有的方案枚举出来，然后求min啊，max啊，但是dp优化是枚举类，一次枚举一类，相当于给全校同学统计人数，暴力枚举是一个同学一个同学的枚举，而dp是一个班一个班的枚举，所以dp会优化一些时间复杂度；

状态计算：化整为零，也是集合的划分加计算，既然一类一类的枚举可以加快速度，当然想每次都一类一类的枚举了，但是类别不是空来的，也需要推导和计算；对这一类来说，把它拥有的子集划分好，求出各个子集的答案，这一类的答案就有了

例1：01背包

题意：给n件物品以及各自的价值，每件物品只有一个且只能取一次，给出背包容量v，问在这n件物品中可以取得的最大价值；

按照闫式dp分析法来，

第一步：化零为整：状态表示

f[ i ][ j ]: 表示所有只考虑取前i件物品和在背包容量为j的情况下的选法集合 ；

---

（思考：可以理解成所有只考虑取前i件物品和在背包容量为j的情况下的最大价值吗？）：

我感觉是都可以的，因为本来要求的就是f[ n ][ m ]的最大值，所以表示的也是最大值；

---

属性：max，找最大价值；

第二步：化整为零：状态计算

找 f[ i ][ j ]这个集合的最大值，需要划分集合，划分的依据是最后一个不同点，在本题中，即选择最后一个物品的方法，有两种：选第i个物品和不选第i个物品；

划分为完之后要考虑两个原则：不重复和不遗漏；

对于每个物品，只有选和不选，所以不会重复，而且每个f[ i ][ j ]的方案只能是来自选和不选第i个物品，所以也不会遗漏；

接下来就是求f[ i ][ j ]的最大值，划分好集合了，我们只需要求出左边集合的最大值，和右边集合的最大值，然后两者在取max，即为f[ i ][ j ]的最大值；

然后求左右子集最大值：

求子集的最大值一般从集合定义下手：

左子集表示不选第i个物品，所以表示的是从1~i-1选，且体积<=j的集合的最大值，这其实就是

f[ i-1 ][ j ]，理解透彻集合定义！

右子集稍微麻烦点：

右子集表示选第i个物品的所有方案，

怎么求这样所有方案的最大值呢，也就是怎么求右子集的最大值呢？

找这些方案的特点（性质）：①最后总是取i，②i之前的方案随便选；

第①点是不会变的，价值就是i物品的价值wi，所以求最大值，只能求前边不确定部分的最大值；

这样想非常重要，因为直接决定了我们像前边不确定部分的集合：前边不确定的部分集合的含义：

从1~i-1选，体积<=j-vi（因为我们已经确定拿了i物品）的集合的最大值，也就是f[ i-1 ][ j -vi ]；

因此，整个右子集的最大值就是变化部分的最大值 不变部分的值：f[ i-1 ][ j -vi ] wi

至此，我们就可以写出f[ i ][ j ]= max(f[ i-1 ][ j ] ， f[ i-1 ][ j-vi] wi)也就是状态转移方程；

有一点需要注意：这是在j>=vi的情况下才可以取第i个物品，所有j<vi右子集就是空的，需要特判一下；

在进行完整个分析过程后，然后再去想可以优化的地方：

此题时间上无法优化，只能优化空间，对于i这一维来说，只用到i和i-1可以用滚动数组优化，

对于j这维来说，我们可以用体积由大到小循环：

for( int j = v; j >= vi ; j-- ) f[ j ] = max ( f[ j ], f[ j-vi ] wi );倒循环的原理：因为我们用到是上一层的

f[ j ]（f[ i-1 ][ j ]）所以这样更新的话，j从大到小遍历，j-vi就会先保存着上一层的结果，也就是

f[ i-1 ][ j ]（因为没更新嘛），就可以被正确的更新；这样得到的也是正确答案；

朴素代码：

1.  
   #include<bits/stdc .h>
2.  
   #define rep1(i,a,n) for(int i=a;i<n;i )
3.  
   #define rep2(i,a,n) for(int i=a;i<=n;i )
4.  
   #define per1(i,n,a) for(int i=n;i>a;i--)
5.  
   #define per2(i,n,a) for(int i=n;i>=a;i--)
6.  
   #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
7.  
   #define INF 0x3f3f3f3f
8.  
   #define pb push_back
9.  
   using namespace std;
10.  
    typedef long long ll;
11.  
    typedef pair<int,int> PII;
12.  
    typedef double db;
13.  
    const int N=1e3 10;
14.  
    int n,v;
15.  
    int f[N][N];
16.  
     
17.  
    signed main()
18.  
    {
19.  
    quick_cin();
20.  
    cin>>n>>v;
21.  
    rep2(i,1,n)
22.  
    {
23.  
    int vi,wi;
24.  
    cin>>vi>>wi;
25.  
    rep2(j,1,v)
26.  
    {
27.  
    if(j>=vi)f[i][j]=max(f[i-1][j],f[i-1][j-vi] wi);
28.  
    else f[i][j]=f[i-1][j];
29.  
    }
30.  
    }
31.  
    cout<<f[n][v];
32.  
    return 0;
33.  
    }

优化一维后的代码：

1.  
   #include<bits/stdc .h>
2.  
   #define rep1(i,a,n) for(int i=a;i<n;i )
3.  
   #define rep2(i,a,n) for(int i=a;i<=n;i )
4.  
   #define per1(i,n,a) for(int i=n;i>a;i--)
5.  
   #define per2(i,n,a) for(int i=n;i>=a;i--)
6.  
   #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
7.  
   #define INF 0x3f3f3f3f
8.  
   #define pb push_back
9.  
   using namespace std;
10.  
    typedef long long ll;
11.  
    typedef pair<int,int> PII;
12.  
    typedef double db;
13.  
    const int N=1e3 10;
14.  
    int n,v;
15.  
    int f[N];
16.  
     
17.  
    signed main()
18.  
    {
19.  
    quick_cin();
20.  
    cin>>n>>v;
21.  
    rep2(i,1,n)
22.  
    {
23.  
    int vi,wi;
24.  
    cin>>vi>>wi;
25.  
    per2(j,v,vi)f[j]=max(f[j],f[j-vi] wi);
26.  
    }
27.  
    cout<<f[v];
28.  
    return 0;
29.  
    }
30.  
     

例2：完全背包问题

题意：和01背包类似，只是每件物品变成可以取无限次；

依旧按照闫式dp分析法来：

第一步：状态表示

f[ i ][ j ]: 表示所有只考虑取前i件物品和在背包容量为j的情况下的选法集合 ；

属性：max，找最大价值；

第二步：化整为零：状态计算

找 f[ i ][ j ]这个集合的最大值，需要划分集合，划分的依据是最后一个不同点，在本题中，即选择最后一个物品的方法，有两种：选第i个物品和不选第i个物品；

然后开始集合划分：（这是我卡到的点）

但是这里左子集和01背包一样，不选第i个物品：f[ i-1 ][ j ]

右子集和01背包就不一样了，前i-1个物品都选，但是对于第i物品：不只是选1个i物品，它包括选一个，选两个，一直到选不下

集合划分好后应该是这样子

然后对所有子集求取max

f[ i ][ j ] = max (f[ i-1 ][ j ], f[ i-1 ][ j-v ] w,f[ i-1 ][ j-2v ] 2w ......)

max只能比较两个，所以这样写的话，要再多重循环，3重循环一般就会tle，这里需要优化一下，需要对集合定义敏感和公式推导敏感；

根绝定义，来看f[ i ][ j-v ]，它的求法应该是

f[ i ][ j-v ] = max(f [i-1][ j-v] ,f[ i-1][ j-2v ] w, f[ i-1 ][ j-3v ] 2w .....)

观察得出： max(f[ i-1 ][ j-v ] w,f[ i-1 ][ j-2v ] 2w ......) = f[ i ][ j-v ] w

所以 f[ i ][ j ] = max (f[ i-1][ j ], f[ i ][ j-v ] w )

朴素代码：

1.  
   #include<bits/stdc .h>
2.  
   #define rep1(i,a,n) for(register int i=a;i<n;i )
3.  
   #define rep2(i,a,n) for(register int i=a;i<=n;i )
4.  
   #define per1(i,n,a) for(register int i=n;i>a;i--)
5.  
   #define per2(i,n,a) for(register int i=n;i>=a;i--)
6.  
   #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
7.  
   #define INF 0x3f3f3f3f
8.  
   #define pb push_back
9.  
   using namespace std;
10.  
    typedef long long ll;
11.  
    typedef pair<int,int> PII;
12.  
    typedef double db;
13.  
    const int N=1e3 10;
14.  
    int n,v;
15.  
    int f[N][N];
16.  
     
17.  
    signed main()
18.  
    {
19.  
    quick_cin();
20.  
    cin>>n>>v;
21.  
    rep2(i,1,n)
22.  
    {
23.  
    int vi,wi;cin>>vi>>wi;
24.  
    rep2(j,1,v)
25.  
    {
26.  
    f[i][j]=f[i-1][j];
27.  
    if(j>=vi)f[i][j]=max(f[i-1][j],f[i][j-vi] wi);
28.  
    }
29.  
    }
30.  
    cout<<f[n][v];
31.  
    return 0;
32.  
    }
33.  
     

优化一维后的代码：

先看二维公式：

f[i][j]=f[i-1][j];
 if(j>=vi)f[i][j]=max(f[i-1][j],f[i][j-vi] wi);

前边的可以不用管，f[j]=f[j]即可；

后边的 f[j-v]用的是第i层也就是当前这一层的数值，而j-vi比j小，所以先更新，所以f [j]用到的就是当前这层，所以f[j]=max(f[j],f[j-vi] wi)是可以的，并且正着循环即可；（对比01背包：01背包是倒循环，因为更新f[j]用到的是上一层的f[j-vi]而 j-vi 比 j 小，所以 保证 j-vi 后更新，即可保证为上一层的 f[ j-vi ] 所以倒循环）

1.  
   #include<bits/stdc .h>
2.  
   #define rep1(i,a,n) for(register int i=a;i<n;i )
3.  
   #define rep2(i,a,n) for(register int i=a;i<=n;i )
4.  
   #define per1(i,n,a) for(register int i=n;i>a;i--)
5.  
   #define per2(i,n,a) for(register int i=n;i>=a;i--)
6.  
   #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
7.  
   #define INF 0x3f3f3f3f
8.  
   #define pb push_back
9.  
   using namespace std;
10.  
    typedef long long ll;
11.  
    typedef pair<int,int> PII;
12.  
    typedef double db;
13.  
    const int N=1e3 10;
14.  
    int n,v;
15.  
    int f[N];
16.  
     
17.  
    signed main()
18.  
    {
19.  
    quick_cin();
20.  
    cin>>n>>v;
21.  
    rep2(i,1,n)
22.  
    {
23.  
    int vi,wi;cin>>vi>>wi;
24.  
    rep2(j,1,v)
25.  
    {
26.  
    f[j]=f[j];
27.  
    if(j>=vi)f[j]=max(f[j],f[j-vi] wi);
28.  
    }
29.  
    }
30.  
    cout<<f[v];
31.  
    return 0;
32.  
    }

 中间写法还可以简化，因为有等价部分；

1.  
   #include<bits/stdc .h>
2.  
   #define rep1(i,a,n) for(register int i=a;i<n;i )
3.  
   #define rep2(i,a,n) for(register int i=a;i<=n;i )
4.  
   #define per1(i,n,a) for(register int i=n;i>a;i--)
5.  
   #define per2(i,n,a) for(register int i=n;i>=a;i--)
6.  
   #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
7.  
   #define INF 0x3f3f3f3f
8.  
   #define pb push_back
9.  
   using namespace std;
10.  
    typedef long long ll;
11.  
    typedef pair<int,int> PII;
12.  
    typedef double db;
13.  
    const int N=1e3 10;
14.  
    int n,v;
15.  
    int f[N];
16.  
    signed main()
17.  
    {
18.  
    quick_cin();
19.  
    cin>>n>>v;
20.  
    rep2(i,1,n)
21.  
    {
22.  
    int vi,wi;cin>>vi>>wi;
23.  
    rep2(j,vi,v)
24.  
    {
25.  
    f[j]=max(f[j],f[j-vi] wi);
26.  
    }
27.  
    }
28.  
    cout<<f[v];
29.  
    return 0;
30.  
    }

例3：石子合并（区间dp）

题意：给出n堆石子，每堆石子有质量，现在开始合并石子，只能合并相邻两堆石子，代价两堆石子质量和，问所有合法的合并中，代价最小是多少；

依旧按照闫式dp分析法：

第一步：状态表示

这个题的状态表示我是只能积累得到的，我自己想不出来，我一开始就是认定f[i]表示合并i堆石子的最小代价，但是不会做；所以不同类的dp问题，集合定义是需要积累的； 

学习新一类的dp的集合定义，也要本质上理解：我们先想所有的方案是什么集合，对于n堆石子，有n-1种合并的方案，接下来是n-2种方案，所以所有的方案就是 （n-1!）枚举每个方案是行不通的，所以定义一类集合，表示一类集合的所有方案，来代表整体；

区间dp问题：定义f[i][j] ：代表i-j区间 的所有方案；本题中，表示将第i -  j堆石子合并成一堆的所有方案；

属性：min

第二步，状态计算：

先集合划分：

对于f[ i ,  j ]这个集合来说，一共包括j-i个子集

第一个是 i， i 1~j

第二个是i~i 1，i 2~j

第三个是i~i 2，i 3~j

.....

最后是i~j-1，j

这样划分的就是不重不漏的所有子集；

然后是计算f[ i , j ]

也就是求出这些子集的最小值，然后加上i~j的和 ，即为 f[ i, j ]

对上述过程作个优化描述：对普遍的第k个数，k∈[ i 1, j-1 ] ；

 每个子集取最小值，刚好与集合定义符合，即f [i , k ] and f[ k 1 , j ] 

所以状态转移方程

f[i][j]=min(f[i][j],f[i][k] f[k 1][j] s[j]-s[i-1]);

代码：

i为左端点，j为右端点，这里len不是区间长度，而是端点数，端点数为1，就是本身，没有合并

所以跳过不枚举，但实际上从i 2开始是跨了一个格子的，所以i 2-1才是枚举i和i 1的方案；所以右端点为i len-1

1.  
   #include<bits/stdc .h>
2.  
   #define rep1(i,a,n) for(register int i=a;i<n;i )
3.  
   #define rep2(i,a,n) for(register int i=a;i<=n;i )
4.  
   #define per1(i,n,a) for(register int i=n;i>a;i--)
5.  
   #define per2(i,n,a) for(register int i=n;i>=a;i--)
6.  
   #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
7.  
   #define INF 0x3f3f3f3f
8.  
   #define pb push_back
9.  
   using namespace std;
10.  
    typedef long long ll;
11.  
    typedef pair<int,int> PII;
12.  
    typedef double db;
13.  
    const int N=1e3 10;
14.  
    int n;
15.  
    int f[N][N],s[N];
16.  
    signed main()
17.  
    {
18.  
    quick_cin();
19.  
    cin>>n;
20.  
    rep2(i,1,n)
21.  
    {
22.  
    int x;cin>>x;
23.  
    s[i]=s[i-1] x;
24.  
    }
25.  
    rep2(len,2,n)
26.  
    {
27.  
    for( int i=1;i len-1<=n;i )
28.  
    {
29.  
    int j=i len-1;
30.  
    f[i][j]=INT_MAX;
31.  
    rep1(k,i,j)f[i][j]=min(f[i][j],f[i][k] f[k 1][j] s[j]-s[i-1]);
32.  
    }
33.  
    }
34.  
    cout<<f[1][n];
35.  
    return 0;
36.  
    }
37.  
     

但如果把区间长度就看成实际的长度，就很好理解了，

len 从1到n-1，n个端点之间n-1条线段；

右端点就是i len了；

1.  
   #include<bits/stdc .h>
2.  
   #define rep1(i,a,n) for(register int i=a;i<n;i )
3.  
   #define rep2(i,a,n) for(register int i=a;i<=n;i )
4.  
   #define per1(i,n,a) for(register int i=n;i>a;i--)
5.  
   #define per2(i,n,a) for(register int i=n;i>=a;i--)
6.  
   #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
7.  
   #define INF 0x3f3f3f3f
8.  
   #define pb push_back
9.  
   using namespace std;
10.  
    typedef long long ll;
11.  
    typedef pair<int,int> PII;
12.  
    typedef double db;
13.  
    const int N=1e3 10;
14.  
    int n;
15.  
    int f[N][N],s[N];
16.  
    signed main()
17.  
    {
18.  
    quick_cin();
19.  
    cin>>n;
20.  
    rep2(i,1,n)
21.  
    {
22.  
    int x;cin>>x;
23.  
    s[i]=s[i-1] x;
24.  
    }
25.  
    rep2(len,1,n-1)
26.  
    {
27.  
    int i,j;
28.  
    for( i=1;i len<=n;i )
29.  
    {
30.  
    j=i len;
31.  
    f[i][j]=INT_MAX;
32.  
    rep1(k,i,j)f[i][j]=min(f[i][j],f[i][k] f[k 1][j] s[j]-s[i-1]);
33.  
    }
34.  
    }
35.  
    cout<<f[1][n];
36.  
    return 0;
37.  
    }

例4：最长公共子序列

题意：给出a字符串和b字符串，问a和b的最长公共子序列的长度是多少；

依旧按照闫式dp分析法：
第一步：状态表示：

（这个题的状态表示真的要积累啊，太难想到了）

f[ i , j ] 表示a[1~i ] , b[1~j ] 的 最长公共子序列的长度；

属性：max

第二步：状态计算：
集合划分：依旧按照一般思路想最后的不同点，

此题有两个，ai和bj

ai选与不选，bj选与不选，所以共四个子集

 （左边是ai，右边是bj，0代表不选，1代表选）

所以这样划分是不重不漏地；

然后开始计算子集最大值，即求f[ i , j ]：
对于‘00’来说：ai和bj都不选，该子集的最大值刚好与定义符合，即f[ i-1, j-1 ]

对于'11'来说：ai和bj都选，也就是ai==bj，其实就是f[ i-1 , j-1 ] 1;

麻烦的是‘01’和‘10’子集：

先说‘01’子集：不选ai选bj，自然联想到f[ i-1 , j ]来看 f[ i-1 , j ]：它的子集中是完全包括了‘01’集合的，但是会多出来，但是还有，这些多出来的也是在f[ i , j ]集合里的，对计算f [ i , j ]并没有影响；

所以可以用f [ i-1 , j ]来覆盖 ‘01’子集，虽然他俩并不完全等价，但是对结果是没有影响的；

对于‘10’子集来说，同理，可以用f[ i, j-1 ]来覆盖 '10'子集；

然后就是对四个子集取max，即为f[ i, j ]

但是求法上还可以优化点写法，因为f[ i-1 , j- 1] 肯定∈f[i , j-1 ] and f[ i-1 , j ] 根据集合定义，很明显可以发现，所以取max时，f[ i-1, j-1 ]就不用考虑了，剩下的3个，‘11‘集合：f[ i-1 , j-1 ] 1也特殊，因为只有ai==bj时才会取到；所以写法上就很简单了

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

if（a[i]==b[j])f[ i ][ j ] = max (f [ i ][ j ] , f[ i-1 , j-1 ] 1)

1.  
   #include<bits/stdc .h>
2.  
   #define rep1(i,a,n) for(register int i=a;i<n;i )
3.  
   #define rep2(i,a,n) for(register int i=a;i<=n;i )
4.  
   #define per1(i,n,a) for(register int i=n;i>a;i--)
5.  
   #define per2(i,n,a) for(register int i=n;i>=a;i--)
6.  
   #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
7.  
   #define INF 0x3f3f3f3f
8.  
   #define pb push_back
9.  
   using namespace std;
10.  
    typedef long long ll;
11.  
    typedef pair<int,int> PII;
12.  
    typedef double db;
13.  
    const int N=1e3 10;
14.  
    int n,m;
15.  
    char a[N],b[N];
16.  
    int f[N][N];
17.  
    signed main()
18.  
    {
19.  
    quick_cin();
20.  
    cin>>n>>m>>a 1>>b 1;
21.  
    rep2(i,1,n)
22.  
    rep2(j,1,m)
23.  
    {
24.  
    f[i][j]=max(f[i-1][j],f[i][j-1]);
25.  
    if(a[i]==b[j])f[i][j]=max(f[i][j],f[i-1][j-1] 1);
26.  
    }
27.  
    cout<<f[n][m];
28.  
    return 0;
29.  
    }

例5：整数划分（计数类dp）

题意：给一个正整数n，它可以表示为若干正整数之和，问有几种划分方法； 

eg ：5有7种

首先，可以看成完全背包问题：容量为n的背包，1~n个数，每个数可以取无限，恰好装满被背包的方案数；

依旧按照闫式dp分析法：

第一步：状态表示：

f[ i , j ]表示从1~i中选，恰好装满j的方案集合；

属性：数量；

第二步：状态计算

先划分集合：

和完全背包划分类似；

然后计算f[ i , j ]

f[ i , j ] = f[ i-1 , j ] f[ i-1, j-i ] f[ i-1 ,j-2*i ] f[ i-1 , j-3*i ] ... f[ i-1 , j- k*i ]

这样写又需要循环，这里直接借鉴完全背包的优化方式，看f[ i ,j-i ]

f[ i , j-i ] = f[ i-1 , j-i ] f[ i-1, j-2*i ] f[ i-1 , j-3*i ] .. f[ i-1 , j-k*i ]

所以 f[ i, j ] = f[ i-1, j ] f[ i , j - i ]

此题注意初始化，对于1~n来说，容积为0不取，也是一种方案；所以容量从0~n开始循环；

1.  
   #include<bits/stdc .h>
2.  
   #define rep1(i,a,n) for(register int i=a;i<n;i )
3.  
   #define rep2(i,a,n) for(register int i=a;i<=n;i )
4.  
   #define per1(i,n,a) for(register int i=n;i>a;i--)
5.  
   #define per2(i,n,a) for(register int i=n;i>=a;i--)
6.  
   #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
7.  
   #define INF 0x3f3f3f3f
8.  
   #define pb push_back
9.  
   using namespace std;
10.  
    typedef long long ll;
11.  
    typedef pair<int,int> PII;
12.  
    typedef double db;
13.  
    const int N=1e3 10;
14.  
    const int mod=1e9 7;
15.  
    int n,m;
16.  
    char a[N],b[N];
17.  
    int f[N][N];
18.  
    signed main()
19.  
    {
20.  
    quick_cin();
21.  
    cin>>n;
22.  
    rep2(i,0,n)f[i][0]=1;
23.  
    rep2(i,1,n)
24.  
    rep2(j,0,n)
25.  
    {
26.  
    f[i][j]=f[i-1][j]%mod;
27.  
    if(j>=i)f[i][j]=(f[i-1][j] f[i][j-i])%mod;
28.  
    }
29.  
    cout<<f[n][n];
30.  
    return 0;
31.  
    }

优化一维后，原理同完全背包；仅6行代码；

1.  
   #include<bits/stdc .h>
2.  
   #define rep1(i,a,n) for(register int i=a;i<n;i )
3.  
   #define rep2(i,a,n) for(register int i=a;i<=n;i )
4.  
   #define per1(i,n,a) for(register int i=n;i>a;i--)
5.  
   #define per2(i,n,a) for(register int i=n;i>=a;i--)
6.  
   #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
7.  
   #define INF 0x3f3f3f3f
8.  
   #define pb push_back
9.  
   using namespace std;
10.  
    typedef long long ll;
11.  
    typedef pair<int,int> PII;
12.  
    typedef double db;
13.  
    const int N=1e3 10;
14.  
    const int mod=1e9 7;
15.  
    int n,m;
16.  
    char a[N],b[N];
17.  
    int f[N];
18.  
    signed main()
19.  
    {
20.  
    quick_cin();
21.  
    cin>>n;
22.  
    f[0]=1;
23.  
    rep2(i,1,n)
24.  
    rep2(j,i,n)
25.  
    f[j]=(f[j] f[j-i])%mod;
26.  
    cout<<f[n];
27.  
    return 0;
28.  
    }

其次呢，还有另一种状态表示的方法，所以对应另一种解法；

第一步：状态表示：

f[ i , j ] 表示所有总和是i 并且恰好表示出j个数的方案；

属性：数量；

第二步：状态计算；

先集合划分：

直接看y总的划分：按集合中最小的数来划分：

 这样划分有什么好处呢，这样划分肯定是不重不漏地，因为最小值就是1，所以这样划分一定包含了所有满足定义的方案；

从这种划分来看，它这样可以很方表的用定义表示出子集，并且不重不漏，这才是定义以及划分的关键；

然后找左右子集；

先看左子集，它是方案中最小值为1 的集合，也就是这些集合都包含1，所以这些集合都减去个1，

就变成了，和是i-1，且恰好有j-1个数，就是f[ i-1, j-1 ]；

再看右子集：

因为集合中每个数都大于1，所以我可以每个数都减去1，这样就表示为和为i-j，且恰有j个数的方案；即f[ i-j , j ]

这样两个子集都有定义表示出来了；

f[ i , j ] = f[ i-1, j-1 ] f[ i-j , j ]

代码：

1.  
   #include<bits/stdc .h>
2.  
   #define rep1(i,a,n) for(register int i=a;i<n;i )
3.  
   #define rep2(i,a,n) for(register int i=a;i<=n;i )
4.  
   #define per1(i,n,a) for(register int i=n;i>a;i--)
5.  
   #define per2(i,n,a) for(register int i=n;i>=a;i--)
6.  
   #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
7.  
   #define INF 0x3f3f3f3f
8.  
   #define pb push_back
9.  
   using namespace std;
10.  
    typedef long long ll;
11.  
    typedef pair<int,int> PII;
12.  
    typedef double db;
13.  
    const int N=1e3 10;
14.  
    const int mod=1e9 7;
15.  
    int n,m;
16.  
    int f[N][N];
17.  
    signed main()
18.  
    {
19.  
    quick_cin();
20.  
    cin>>n;
21.  
    f[0][0]=1;
22.  
    rep2(i,1,n)
23.  
    rep2(j,1,i)
24.  
    f[i][j]=(f[i-1][j-1] f[i-j][j])%mod;
25.  
    int ans=0;
26.  
    rep2(i,1,n)ans=(ans f[n][i])%mod;
27.  
    cout<<ans;
28.  
    return 0;
29.  
    }

例6：计数问题（数位统计dp）

题意：给出正整数a，b，求区间[ a , b ]之间的整数的0~9的出现次数；

 逐个枚举肯定不行，按照dp的思想要按类来枚举，这里之间上定义：
count（x，i）表示1~x中，i的出现次数；

所以对于i∈0~9，用count（b，i）-count（a-1，i）即为a到b之间的数中，0~9出现的次数；

count函数实现：

主要是分情况讨论：

上边是普遍情况的分析，下边考虑特殊情况，

 特殊情况：

x在首位：无（1）方案；

x=0：则xxx∈[1，abc-1] 所以对应少了一个1000；

x=0且在首位，从第二位开始；

1.  
   因为abcdefg 存到数组里是gfedcba，所以倒循环且下标n-1；
2.  
   for(int i=n-1-!x;i>=0;i--)//！x是若x==0则从第二位开始枚举
3.  
   {
4.  
   if(i<n-1)//首位无此类方案，只有第二位开始才有；
5.  
   {
6.  
   res =get(num,n-1,i 1)*power10(i);
7.  
   if(!x)res-=power10(i);//x=0,第一类方案少1个10的i次方；
8.  
   }
9.  
   //num[i]<x 无解，不用写；
10.  
    if(num[i]==x)res =get(num,i-1,0) 1;//注意 1（自身==x也是一种）
11.  
    else if(num[i]>x)res =power10(i);//后边随便取，所以10的i次方；
12.  
    }

1.  
   #include<bits/stdc .h>
2.  
   #define rep1(i,a,n) for(register int i=a;i<n;i )
3.  
   #define rep2(i,a,n) for(register int i=a;i<=n;i )
4.  
   #define per1(i,n,a) for(register int i=n;i>a;i--)
5.  
   #define per2(i,n,a) for(register int i=n;i>=a;i--)
6.  
   #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
7.  
   #define INF 0x3f3f3f3f
8.  
   #define pb push_back
9.  
   using namespace std;
10.  
    typedef long long ll;
11.  
    typedef pair<int,int> PII;
12.  
    typedef double db;
13.  
    const int N=10;
14.  
    int get(vector<int>num,int l,int r)
15.  
    {
16.  
    int res=0;
17.  
    per2(i,l,r)res=res*10 num[i];
18.  
    return res;
19.  
    }
20.  
    int power10(int x)
21.  
    {
22.  
    int res=1;
23.  
    while(x--)res*=10;
24.  
    return res;
25.  
    }
26.  
    int count(int n,int x)
27.  
    {
28.  
    if(!n)return 0;
29.  
    vector<int>num;
30.  
    while(n)
31.  
    {
32.  
    num.pb(n%10);
33.  
    n/=10;
34.  
    }
35.  
    n=num.size();
36.  
    int res=0;
37.  
    for(int i=n-1-!x;i>=0;i--)
38.  
    {
39.  
    if(i<n-1)
40.  
    {
41.  
    res =get(num,n-1,i 1)*power10(i);
42.  
    if(!x)res-=power10(i);
43.  
    }
44.  
    if(num[i]==x)res =get(num,i-1,0) 1;
45.  
    else if(num[i]>x)res =power10(i);
46.  
    }
47.  
    return res;
48.  
    }
49.  
    signed main()
50.  
    {
51.  
    quick_cin();
52.  
    int a,b;
53.  
    while(cin>>a>>b,a)
54.  
    {
55.  
    if(a>b)swap(a,b);
56.  
    rep2(i,0,9)cout<<count(b,i)-count(a-1,i)<<' ';
57.  
    cout<<endl;
58.  
    }
59.  
    return 0;
60.  
    }

例7：蒙德里安的梦想（状态压缩dp）

 题意：

核心：（数据范围很小，可以用二进制数表示状态）

先放横着的，在放竖着的 ；这样只要我横着放完，剩下的竖的只要嵌进去就行，所以竖着的只能是这样，即总方案数是横着放的合法方案数；如何判断方案是否合法呢，只需要判断每一列剩下的连续空棋盘数是否为偶数，偶数则合法，否则不合法；

按照闫式dp分析法：

第一步：状态表示：
f[ i , j ] 表示 前i-1列已经放好，从第 i-1 列伸到第 i 列的状态是 j 的所有方案；

属性：数量；

第二步：状态计算：

因为属性是数量，所以f[ i , j ]是所有子集方案之和;

先划分集合：

对于每一行，都有伸或者不伸到第i列两种选择，所以共2^n种方案；

这样划分也是不重不漏的；

这里是表示状态是可以状态压缩的，用个长度为n的二进制数，eg:01000...；表示第二行 伸到第i列，而其他所有行都不伸到第i列的一种方案；

划分好子集后，需要去求子集，进而才能求f[ i , j  ]，也就是找状态转移；

既然第 i 列固定了，我们需要看 第i-2 列是怎么转移到到第 i-1列的（看最后转移过来的状态）。假设此时对应的状态是k（第i-2列到第i-1列伸出来的二进制数，比如00100），k也是一个二进制数，1表示哪几行小方块是横着伸出来的，0表示哪几行不是横着伸出来的。

它刚好就是f[ i -1 ,  k ] , 但是，这个k是有条件限制的，也就是需要是合法的方案；

①k和j不能在同一行，即j&k==0，原因：因为从i-1列到第i列是横着摆放的12的方块，那么i-2列到i-1列就不能是横着摆放的，否则就是1 3的方块了！这与题意矛盾。所以 k和j不能位于同一行！

既然从第i-1列到第i列横着摆的，和第i-2列到第i-1列横着摆的都确定了，那么第i-1列 空着的格子就确定了，这些空着的格子将来用作竖着放。如果 某一列有这些空着的位置，那么该列所有连续的空着的位置长度必须是偶数。

满足这两个条件，f[ i ][ j ] = f[ i-1 ][ k ]； 

对这两个条件直接全部枚举可能会tle，这里优化下对条件的筛选；

1.  
   #include<bits/stdc .h>
2.  
   #define rep1(i,a,n) for(register int i=a;i<n;i )
3.  
   #define rep2(i,a,n) for(register int i=a;i<=n;i )
4.  
   #define per1(i,n,a) for(register int i=n;i>a;i--)
5.  
   #define per2(i,n,a) for(register int i=n;i>=a;i--)
6.  
   #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
7.  
   #define INF 0x3f3f3f3f
8.  
   #define pb push_back
9.  
   using namespace std;
10.  
    typedef long long ll;
11.  
    typedef pair<int,int> PII;
12.  
    typedef double db;
13.  
    int n,m;
14.  
    const int N=12,M=1<<N;
15.  
    ll f[N][M];
16.  
    vector<int>state[M];
17.  
    bool st[M];
18.  
    signed main()
19.  
    {
20.  
    quick_cin();
21.  
    while(cin>>n>>m,n||m)
22.  
    {
23.  
    //第一部分：预处理1
24.  
    //对于每种状态，先预处理每列不能有奇数个连续的0
25.  
    rep1(i,0,1<<n)
26.  
    {
27.  
    int cnt=0;//记录连续的0的个数
28.  
    bool isvalid=1;// 某种状态没有奇数个连续的0则标记为true
29.  
    rep1(j,0,n)//遍历这一列，从上到下
30.  
    {
31.  
    if(i>>j&1)//i>>j位运算，表示i（i在此处是一种状态）的二进制数的第j位； &1为
32.  
    //判断该位是否为1，如果为1进入if
33.  
    {
34.  
    if(cnt&1)//这一位为1，看前面连续的0的个数，如果是奇数（cnt &1为真）则该
35.  
    状态不合法
36.  
    {
37.  
    isvalid=0;
38.  
    break;
39.  
    }
40.  
    cnt=0;// 既然该位是1，并且前面不是奇数个0（经过上面的if判断），计数器清
41.  
    零。//其实清不清零没有影响
42.  
    }
43.  
    else cnt ;
44.  
    }
45.  
    if(cnt&1)isvalid=0;
46.  
    st[i]=isvalid;//状态i是否有奇数个连续的0的情况,输入到数组st中
47.  
    }
48.  
    //下面来看进一步的判断：看第i-2列伸出来的和第i-1列伸出去的是否冲突
49.  
    rep1(j,0,1<<n) //对于第i列的所有状态
50.  
    {
51.  
    state[j].clear(); //清空上次操作遗留的状态，防止影响本次状态。
52.  
    rep1(k,0,1<<n)//对于第i-1列所有状态
53.  
    {
54.  
    if((j&k)==0&&st[j|k])state[j].pb(k); // 第i-2列伸出来的 和第i-1列伸出来
55.  
    的不冲突(不在同一行)
56.  
    //解释一下st[j | k]
57.  
    //已经知道st[]数组表示的是这一列没有连续奇数个0的情况，
58.  
    //我们要考虑的是第i-1列（第i-1列是这里的主体）中从第i-2列横插过来的，还要考
59.  
    虑自己这一列（i-1列）横插到第i列的
60.  
    //比如 第i-2列插过来的是k=10101，第i-1列插出去到第i列的是 j =01000，
61.  
    //那么合在第i-1列，到底有多少个1呢？自然想到的就是这两个操作共同的结果：两个
62.  
    状态或。 j | k = 01000 | 10101 = 11101
63.  
    //这个 j|k 就是当前 第i-1列的到底有几个1，即哪几行是横着放格子的
64.  
    }
65.  
    }
66.  
    memset(f,0,sizeof f);
67.  
    f[0][0]=1;
68.  
    rep2(i,1,m)
69.  
    rep1(j,0,1<<n)
70.  
    for(auto k:state[j])
71.  
    f[i][j] =f[i-1][k];
72.  
    cout<<f[m][0]<<endl;
73.  
    }
74.  
    return 0;
75.  
    }

例8：砝码称重（背包问题）

题意：

 从题目描述中可以发现，这是一个有限制的选择问题，对于每个砝码，都有3种选择，放左边，放右边和不放；有限制的选择问题又名背包问题；所以直接闫式dp分析法：

第一步：状态表示：
f[ i ,  j ]从前i个物品选，且总重量为j的所有方案的集合；

所以最终答案是f[n][1~sum]中不为空集的数量；

属性：是否为空；此题只要有j的集合，就存在j，ans就 ；

第二步：状态计算：

先集合划分：

根据第i个物品的3种选法，集合可以划分为3类：

第一类：第i个物品放左边（ ）：

改集合是，第i个物品必选，且总重量为j；（本来以为这不就是f[i , j ]吗？但是一定要严格和集合定义契合，f[ i ,  j ]表示从前i个物品选，前i个物品怎么选是不用管的，！！）既然第i个物品确定了，不妨看前边，前边i-1随便选，且选了第i个物品重量为j，那么不选就是前i-1选，重量为j-wi；

所以第一类集合空不空就是看f[ i-1, j-wi] 也就是第一类集合是f[ i-1, j-wi ]；

第二类集合：第i个物品放右边（-）：

同第一类：f[ i-1, j wi ];

第三类：第i个物品不选：f [ i-1, j ]；

同时本题有个性质，只统计正整数，也就是-j和j其实都是 j，只是位置不同，所以对于这个取绝对值就好；并且从0到sum 开始遍历即可，不用从-sum到sum

1.  
   #include<bits/stdc .h>
2.  
   #define rep1(i,a,n) for(register ll i=a;i<n;i )
3.  
   #define rep2(i,a,n) for(register ll i=a;i<=n;i )
4.  
   #define per1(i,n,a) for(register ll i=n;i>a;i--)
5.  
   #define per2(i,n,a) for(register ll i=n;i>=a;i--)
6.  
   #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
7.  
   #define INF 0x3f3f3f3f
8.  
   #define pb push_back
9.  
   using namespace std;
10.  
    typedef long long ll;
11.  
    typedef pair<int,int> PII;
12.  
    typedef double db;
13.  
    const int N=1e6 10;
14.  
    int a[N];
15.  
    bool f[110][N];
16.  
    signed main()
17.  
    {
18.  
    quick_cin();
19.  
    int n;
20.  
    cin>>n;
21.  
    ll sum=0,ans=0;
22.  
    rep2(i,1,n)cin>>a[i],sum =a[i];
23.  
    f[0][0]=1;
24.  
    rep2(i,1,n)
25.  
    rep2(j,0,sum)
26.  
    f[i][j]=f[i-1][j]||f[i-1][j a[i]]||f[i-1][abs(j-a[i])];
27.  
    rep2(j,1,sum)
28.  
    if(f[n][j])ans ;
29.  
    cout<<ans;
30.  
    return 0;
31.  
    }

此题还可以用记忆化搜索：

个人认为写递归更好理解，也比较容易上手（ps：dp中集合定义和划分集合太难想辣！）

对于少数的选择（2到3个？），可以用递归枚举的，加上dp优化，可以上记忆化搜索一试；

那么像完全背包，每个物品选无限次，你是肯定无法用dfs做的；

1.  
   #include<bits/stdc .h>
2.  
   #define rep1(i,a,n) for(register ll i=a;i<n;i )
3.  
   #define rep2(i,a,n) for(register ll i=a;i<=n;i )
4.  
   #define per1(i,n,a) for(register ll i=n;i>a;i--)
5.  
   #define per2(i,n,a) for(register ll i=n;i>=a;i--)
6.  
   #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
7.  
   #define INF 0x3f3f3f3f
8.  
   #define pb push_back
9.  
   using namespace std;
10.  
    typedef long long ll;
11.  
    typedef pair<int,int> PII;
12.  
    typedef double db;
13.  
    const int N=1e6 10;
14.  
    int a[N];
15.  
    int n;
16.  
    bool f[110][N];
17.  
    bool res[N];
18.  
    void dfs(int x,int sum)
19.  
    {
20.  
    if(f[x][sum])return;
21.  
    f[x][sum]=1;
22.  
    res[sum]=1;
23.  
    if(x>n)return;
24.  
    dfs(x 1,sum a[x]);
25.  
    dfs(x 1,abs(sum-a[x]));
26.  
    dfs(x 1,sum);
27.  
    }
28.  
    signed main()
29.  
    {
30.  
    quick_cin();
31.  
    cin>>n;
32.  
    ll sum=0,ans=0;
33.  
    rep2(i,1,n)cin>>a[i],sum =a[i];
34.  
    dfs(1,0);
35.  
    rep2(i,1,sum)if(res[i])ans ;
36.  
    cout<<ans;
37.  
    return 0;
38.  
    }

例9：滑雪（记忆化搜索）

题意：

直接dfs会爆tle，所以用dp来做；

闫式dp分析法：
第一步：

状态表示：

f[ i, j ] 表示从当前位置开始滑能滑到的最远路径；

属性：max

第二步：

状态计算：
先划分集合：
很明显，根据集合定义可以划分为四个部分：

然后计算子集：

拿向上滑举例：

i , j → （滑到） i-1 , j → .. .. . . .只有第一步滑到 i-1 ,j 是确定的，剩下的都确定，又因为求的是最大值，把每个集合都减1对答案没有影响，所以可以把第一步去掉来看，就是从i-1 , j 滑到的 最远距离，即f[ i-1 ,j ] 同理可以得到四个子集；

注意，4个子集并不是每个都存在，必须满足边界和高度条件；

所以答案就是对每个f[ i , j ] 取max，就是最远的；

1.  
   #include<bits/stdc .h>
2.  
   #define rep1(i,a,n) for(register ll i=a;i<n;i )
3.  
   #define rep2(i,a,n) for(register ll i=a;i<=n;i )
4.  
   #define per1(i,n,a) for(register ll i=n;i>a;i--)
5.  
   #define per2(i,n,a) for(register ll i=n;i>=a;i--)
6.  
   #define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
7.  
   #define INF 0x3f3f3f3f
8.  
   #define pb push_back
9.  
   using namespace std;
10.  
    typedef long long ll;
11.  
    typedef pair<int,int> PII;
12.  
    typedef double db;
13.  
    const int N=300 10;
14.  
    int f[N][N];
15.  
    int a[N][N];
16.  
    int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
17.  
    int r,c;
18.  
    int ans;
19.  
    int dp(int x,int y)
20.  
    {
21.  
    if(f[x][y])return f[x][y];
22.  
    f[x][y]=1;
23.  
    rep2(i,0,3)
24.  
    {
25.  
    int x1=x dx[i];
26.  
    int y1=y dy[i];
27.  
    if(x1>0&&x1<=r&&y1>0&&y1<=c&&a[x1][y1]<a[x][y])
28.  
    {
29.  
    f[x][y]=max(f[x][y],dp(x1,y1) 1);
30.  
    }
31.  
    }
32.  
    return f[x][y];
33.  
    }
34.  
    signed main()
35.  
    {
36.  
    quick_cin();
37.  
    cin>>r>>c;
38.  
    rep2(i,1,r)
39.  
    rep2(j,1,c)cin>>a[i][j];
40.  
    memset(f,0,sizeof f);
41.  
    rep2(i,1,r)
42.  
    {
43.  
    rep2(j,1,c)
44.  
    {
45.  
    ans=max(ans,dp(i,j));
46.  
    }
47.  
    }
48.  
    cout<<ans;
49.  
    return 0;
50.  
    }

思考：如果从dfs角度来理解优化：对于每个点都需要dfs是肯定的，但是问题在于进入dfs后，搜到了一个点，之前计算过，我们没必要计算了其实，假如从（2，4）搜到（2，3），我们如果算过了（2，3）这个点，那么再次碰到它时直接调用它的值就行，没有必要再算，所以需要f[][]来储存算过的值，搜到了直接调用就行；

所以深度搜索 dp优化-》记忆化搜索（递归式动态规划）；

这篇好文章是转载于：学新通技术网