整数划分 dp

柔情只为你懂 2022-05-27 23:26 321阅读 0赞

蒜头君特别喜欢数学。今天，蒜头君突发奇想：如果想要把一个正整数 nn 分解成不多于 kk 个正整数相加的形式，那么一共有多少种分解的方式呢？

蒜头君觉得这个问题实在是太难了，于是他想让你帮帮忙。

输入格式

共一行，包含两个整数 n(1 \leq n \leq 300)n(1≤n≤300) 和 k(1 \leq k \leq 300)k(1≤k≤300)，含义如题意所示。

输出格式

一个数字，代表所求的方案数。

样例输入

  1. 5 3

样例输出

5

  1. #include<stdio.h>
  2. long long n,k,dp[310][310];
  3. int main()
  4. {
  5.     scanf("%lld %lld",&n,&k);
  6.     for(int i=1; i<=n; i++)
  7.     {
  8.         for(int j=1; j<=k; j++)
  9.         {
  10.             if(i==1||j==1)
  11.                 dp[i][j]=1;
  12.             else if(i<j)
  13.                 dp[i][j]=dp[i][i];
  14.             else if(i>j)
  15.                 dp[i][j]=dp[i-j][j]+dp[i][j-1];
  16.             else
  17.                 dp[i][j]=1+dp[i][j-1];
  18.         }
  19.     }
  20.     long long s=dp[n][k];
  21.     printf("%lld\n",s);
  22.     return 0;
  23. }

发表评论

表情：
评论列表 （有 0 条评论，321人围观）

还没有评论，来说两句吧...

相关阅读

    相关 整数划分问题

    根据n和m的关系，考虑以下几种情况：         （1）当 n = 1 时，不论m的值为多少（m > 0 )，只有一种划分即 \{ 1 \};         (...

    墨蓝墨蓝/ 0 赞/ 194 阅读

    相关 整数划分问题

    题目描述 计算将一个给定的正整数划分为一系列正整数的和的方案数，称为整数的划分问题，例如，当给定正整数为6时，可以有如下划分： 6=6； 6=5+1； 6=4+2=4+

    清疚清疚/ 0 赞/ 183 阅读

    相关 整数划分 区间dp

    题目链接[点击打开链接][Link 1] 题目大意是说有一个不超过二十位的数字，要将这个数字划分成n段，最后让这n段数字相乘，问怎么划分使乘积最大。 分析： 一

    怼烎@怼烎@/ 0 赞/ 388 阅读

    相关 整数划分问题

    问题描述：将以正整数n表示成一系列正整数之和。 输入：整数N 输出：划分方法的总数。 //n为输入的整数，不同划分中最大加数不超过m，返回划分方法的总数。 int q(

    小咪咪小咪咪/ 0 赞/ 301 阅读

    相关 整数划分--DP

    5. [数的划分][Link 1] 问题描述 　　将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。 　　例如：n=7，k=3，下面三种分法被认为是相同

    红太狼红太狼/ 0 赞/ 342 阅读

    相关 整数划分 dp

    蒜头君特别喜欢数学。今天，蒜头君突发奇想：如果想要把一个正整数 nn 分解成不多于 kk 个正整数相加的形式，那么一共有多少种分解的方式呢？ 蒜头君觉得这个问题实在是太难了，

    柔情只为你懂柔情只为你懂/ 0 赞/ 322 阅读