前往小程序,Get更优阅读体验!
立即前往
发布
社区首页 >专栏 >PTA-------整数分解

PTA-------整数分解

作者头像
用户11396661
发布2024-12-09 14:45:15
发布2024-12-09 14:45:15
470
举报
文章被收录于专栏:C++开发

1.问题描述.

2.代码实现

代码语言:javascript
复制
#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;
}

3.代码理解

拿题目的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.按上面步骤一直往下执行就能完成题目要求。

天上的星星很多,可是多不过我的思念 。雨中的雷声很大,可是大不过我的牵挂 。得不到是因为不属于你,放不下是因为你不甘心。失去所爱,虽然伤心,但失去不爱你的人,又有什么可伤心呢。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-04-19,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1.问题描述.
  • 2.代码实现
  • 3.代码理解
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档