#include <stdio.h>
int fun(int n, int m)
{
int dp[n + 1];
dp[0] = 1;
for (int i = 1; i <= n; i++)
{
dp[i] = 0;
}
for (int i = 1; i <= m; i++) //外层循环 表示最大数为多少。从1开始,到m
{
for (int j = i; j <= n; j++) //内层循环
{
dp[j] = dp[j - i] + dp[j]; //dp[j]会进行更新
}
}
return dp[n];
}
int main()
{
int n, m;
scanf("%d %d", &n , &m );
printf("%d",fun(n,m));
return 0;
}
拿题目的5来说
1.外部循环i为1时.(可以确定最终dp[1]=1,1=1)
最大数为1时,内层循环结束的时候,dp[n]表示整数n当最大数为1时的种数;dp[1]到dp[5]都是1,因为1到5,当最大数为1时,都只能分解1,所以都是1种.dp[1]已经可以确定为1了(1=1);
2.外部循环为(i)2时.(可以确定最终dp[2]=2,2=1+1,2=2)
dp[2]=2.一开始n为2,此时dp[2]=dp[2-2]+1;i=j时,只能为自己本身,所以dp[0]=1,此时dp[2]=1+1=2(2=1+1,2=2);
dp[3]=2.n=3,m=2,dp[3]=dp[3-2]+1;dp[3-]可以理解为当整数为3最大数为2时,因为最大数为2已经确定下来,所以最起码有一个二,所以我们只要看把1分解的种数就可以确定总种数,所以dp[3]=1+1(最大数为2时);
dp[4]=3.dp[4]=dp[4-2]+1=3;因为最大数已经有2了,所以确定剩下的n-m最大数为m的种数就能确定dp[4]的总种数,此时dp[2]=2(2=1+1,2=2)。所以dp[4]=1+1+1+1=1+1+1+2=2+2;
3.按上面步骤一直往下执行就能完成题目要求。
天上的星星很多,可是多不过我的思念 。雨中的雷声很大,可是大不过我的牵挂 。得不到是因为不属于你,放不下是因为你不甘心。失去所爱,虽然伤心,但失去不爱你的人,又有什么可伤心呢。