当前位置: 代码迷 >> 综合 >> 整数划分 51Nod - 1201 (经典dp)
  详细解决方案

整数划分 51Nod - 1201 (经典dp)

热度:14   发布时间:2023-12-12 14:25:37.0

整数划分 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;
}