http://acm.hdu.edu.cn/showproblem.php?pid=1028
dp[i][j]表示数值为i,然后最小拆分的那个数是j的时候的总和。
1 = 1
2 = 1 + 1 、 2 = 2
3 = 1 + 1 + 1、 3 = 2 + 1、 3 = 3
那么可以分两类,
1、最小拆分数是j,这个时候dp[i][j] = dp[i - j][j]。加一个数j,使得它变成i
2、最小拆分数严格大于j,这个时候就没得加上j了。就是dp[i][j + 1]
所以dp[i][j] = dp[i - j][j] + dp[i][j + 1]; (加上dp[i][j + 1]是前缀和的意思)
dp[2][1]就是2中的两条等式,然后dp[3][1] = dp[2][1] + dp[3][2]
其中dp[2][1]中有两条式子,所以每个式子加上一个1上去,就是3中前两条式子。
然后dp[3][2]其实就是3 = 3这条,因为3的式子不存在最小拆分数是2的情况。
如果要输出最小拆分数是k的时候有多少种解。
就是dp[val][k] - dp[val][k + 1];
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = + ;
int dp[maxn][maxn];
const int N = ;
void init() {
for (int i = ; i <= N; ++i) {
dp[i][i] = ;
for (int j = i - ; j >= ; --j) {
dp[i][j] = dp[i - j][j] + dp[i][j + ];
}
}
// cout << dp[4][1] - dp[4][2] << endl;
} int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
init();
int n;
while (cin >> n) {
cout << dp[n][] << endl;
}
return ;
}
这题居然可以相当于完全背包,整数划分的题目(可以相同)可以转化为完全背包。
dp[i]表示产生这个数字所拥有的合法方案数。
而加了一维,dp[i][j]这样的话,可以用来判断一些特殊条件,例如相差的值不能大于多少这样子。
http://www.cnblogs.com/liuweimingcprogram/p/7010170.html
http://acm.hdu.edu.cn/showproblem.php?pid=2709 (正常dpMLE)
隐含着dp[i][j]
表示前i个物品,组成j的方案数。只能是前i个物品