整数划分

算法笔记
,

区间dp经典题

题目描述

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
const int N = 1e9+7;
// f[i,j]表示为数字j，用小于等于i的数字的划分方法数
// 那么有递推表达式：   f[i,j] = f[i-1,j] + f[i-1,j-i] + f[i-1,j-2i]+f[i-1,j-3i]+...
//                   f[i,j-i] = f[i-1,j-i]+f[i-1,j-2i]+f[i-1,j-3i]+f[i-1,j-4i]+...
//                   f[i,j] = f[i-1,j] + f[i,j-i]
long long int f[1001][1001];
int n;
int main() {
    scanf("%d", &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] % N;
            if(j >= i) f[i][j] = (f[i][j] + f[i][j-i]) % N;
        }
    }
    printf("%d", f[n][n]);
    return 0;
}

相当于是完全背包问题，重要的还是需要耐心推导表达式。

还有另一种思路：f[i][j]表示的是总和是i，恰好表示成j个数的方案。

那么可以把f[i][j]的集合划分成两个部分，一个是其中任意一个数为1的，一个是其中任意一一个数都严格大于1的。

那么任意一个数都大于1的集合正好与f[i-1][j-1]是一一对应的。

任意一个数都严格大于1的集合与f[i-j][j]也是一一对应的。

因此有状态转移式为：f[i][j]=f[i-1][j-1]+f[i-j][j]。