文章图片
可以转换为完全背包问题
从1~n选择若干个数，使它们的和恰好为n，一共有多少种方案
【动态规划|【动态规划】完全背包（整数划分（方案数））】
dp[i][j]表示从前i个数选若干个数，使它们的和恰好为j的方案数
考虑第i个数选几次
dp[i][j]=dp[i-1][j]+dp[i-1][j-i]+dp[i-1][j-2*i]+...
时间优化：
注意到 dp[i][j-i]=dp[i-1][j-i]+dp[i-1][j-2*i]+dp[i-1][j-3*i]+....
所以dp[i][j]=dp[i-1][j]+dp[i][j-i]
空间优化：
滚动数组
for i 1~n:
for j i~n:dp[j]=dp[j]+dp[j-i]
代码：
int n;
cin>>n;
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int i=1;
i<=n;
i++)
{
for(int j=i;
j<=n;
j++)
{
dp[j]=(dp[j]+dp[j-i])%mod;
}
}
cout<推荐阅读
- 蓝桥杯|2021年第十二届蓝桥杯省赛第二场Python组（真题+解析+代码）（格点）
- 算法|快速幂 教程
- 算法|近似算法的近似率_选择最佳近似最近算法的数据科学家指南
- 蓝桥杯真题省赛2021|蓝桥杯 2021省赛 python 路径
- #|2017年蓝桥杯省赛-承压计算
- 算法刷题|LeetCode刷题笔记-21.合并两个有序链表
- python|第一篇博客，与您共勉
- 蓝桥杯|蓝桥杯python（题目思路即解答（笔记，持续更新））
- 算法|第十届蓝桥杯省赛B组题解记录