刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！

简答题

组合

【题目描述】

输入两个正整数 n 和 m(20 >= m >= n > 0)，n 代表正整数的个数，要求 n 个正整数相加的和为 m，输出满足这个条件的正整数组合有多少。

例如：当 n=4，m=8 时，满足条件的有 5 组(也就是:5+1+1+1=8，4+2+1+1=8，3+3+1+1=8，3+2+2+1=8，2+2+2+2=8，每组组合都由 4 个正整数组成且 4 个正整数的和等于 8)

【输入描述】

分行输入 n 和 m(20>=m>=n>0)

【输出描述】

输出满足这个条件的正整数组合有多少

【输入样例】

4
8

【输出样例】

5

使用微信搜索喵呜刷题，轻松应对考试！

答案：

对于给定的n和m，可以使用动态规划来解决这个问题。

解析：

【喵呜刷题小喵解析】：
这个问题可以通过动态规划来解决。首先，我们定义一个二维数组dp，其中dp[i][j]表示使用i个正整数，其和为j的方案数。

然后，我们可以使用递推式来填充这个数组。对于每个i和j，我们可以考虑使用i-1个正整数，其和为k（其中k的取值范围是[0, j-1]），然后加上一个正整数j-k。这样，dp[i][j]就等于dp[i-1][k]乘以dp[1][j-k]。

最后，我们只需要返回dp[n][m]即可，表示使用n个正整数，其和为m的方案数。

具体来说，动态规划的转移方程如下：

dp[i][j] = sum{dp[i-1][k] * dp[1][j-k] | 0 <= k < j}

其中，dp[1][j]表示使用一个正整数，其和为j的方案数。当j=1时，dp[1][1]=1；当j>1时，dp[1][j]=0。

最后，我们只需要遍历n和m，使用动态规划计算出dp[n][m]即可。
创作类型：
原创

本文链接：组合 【题目描述】 输入两个正整数 n 和 m(20 >= m >= n > 0)，n 代表正整数的

版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！

分享考题
share