整数划分 51 Nod - 1201
将N分为若干个不同整数的和，有多少种不同的划分方式，例如：n = 6，{6} {1,5} {2,4} {1,2,3}，共4种。由于数据较大，输出Mod 10^9 + 7的结果即可。
Input
输入1个数N(1 <= N <= 50000)。
Output
输出划分的数量Mod 10^9 + 7。
Sample Input
6
Sample Output
4
这道题 刚写的时候 使用的 dfs 但是 由于 数据很大 ，所以 会超时 ，想着 优化一下，但是 dfs 与 bfs 本身 就是 比较 费时的 所以 就没写出来，其实 我自己 也想到啦 这道题 很可能是 用 dp 写的， 但是 动态规划方程 想不到 是什么， 去网上 搜了 题解 才明白了， 感觉 真是 好题 所以 写出来跟大家分享一下！
这道题的 动态转移方程为：
dp[ i ][ j ] = dp[ i-j ][ j ] + dp[ i-j ][ j-1 ]
dp[ i ][ j ] 表示 用 j 个数 子 组成 i 的 不同的 组合种类， dp[ i-j ][ j ] 表示 组成 i-j 的 j 个数字 全部都 加上 一个 一 之后 刚好 等于 i 刚好也是 用 j 个数 组成 i 的 不同 组合种类 中的 其中 一部分 种类， dp[ i-j ][ j-1 ] 表示的意思是： 用 j-1 个数 来组成 i-j+1 但是 呢 应为 原来 组成 i-j 的 j 个数 都已经 加上了 一 所以 都比一大 ， 上式之所以仍然写作 i-j 是应为 这里 除了 j-1 个数字 之外 包含了 一个 一 。我也是 想了之后 才明白的 ！
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int mod = 1e9 + 7;int main()
{int n;while(~scanf("%d", &n)){int ans;static int dp[50100][350];memset(dp, 0, sizeof(dp));dp[0][0] = 1;for(int j = 1; j < 350; j++){for(int i = 0; i <= n; i++)if(i - j >= 0)dp[i][j] = (dp[i-j][j] + dp[i-j][j-1]) % mod;}ans = 0;for(int j = 1; j < 350; j++)ans = (ans + dp[n][j]) % mod;printf("%d\n", ans);}return 0;
}