整数划分,性质一的疑惑,n拆分成k个数
程序员文章站
2022-07-15 18:58:55
...
对于整数的拆分中的性质一有不解,在网上搜索的答案中,竟找不到相应的令人满意的解释,郁闷,在群上讨论发现了如此代码,但给出的人又不能做出解释,只好,先记录在案下图,是我自己根据给出的代码进行一定的理解分析。
就发现,,,,,,
哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈,在写博客的过程中,突然明白了,dp[i-j][j]的作用,(我留出对应j个数的一给你,i-j后的数划分j个,给你划分后的数字加一就求得部分答案,)对于dp[i-1][j-1],意思就是,我现在留出一个1,相当于占了一个,那你就去帮我求出减一后(i-1)的拆成(j-1)个数字给我。
然后现在还有疑问的是,就是为什么这样给就不会出现遗漏和重复了,那应该是数学的问题了吧,哎哟我这笨脑子,啧啧啧,想不通。或许是最后给每个加一的是不会影响dp[i-1][j-1]的取法;有待考究。
#include<iostream>
#include<cstdio>
using namespace std;
long long dp[305][305];
int main() {
int n, k;
scanf( "%d%d", &n, &k );
dp[0][0] = 1;
for ( int i = 1 ; i <= n ; ++ i )
{
for ( int j = 1 ; j <= i ; ++ j )
{
if ( i >= j )
{
dp[i][j] = dp[i-1][j-1] + dp[i-j][j];
}
else
{
dp[i][j] = dp[i][i];
}
}
}
long long res = 0;
printf("%d",dp[n][k]);//求性质一
for ( int i = 1 ; i <= k ; i++ )
{
res += dp[n][i];
}
printf("%d",res);//求性质二
return 0;
}
上一篇: K大元素
推荐阅读