动态规划自然数拆分_vlambda技术博客

vlambda
2020-04-22

动态规划自然数拆分

继续动态规划

题目

任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。输入n，输出最终的拆分方法数。

解析

这道题

我们以前

曾经写过题解

不过当时是用

搜索与回溯写的

而这次

是用动态规划

其实我个人仍认为

还是使用搜索与回溯简单一些

用动态规划

不仅不能得出过程

而且很难理解

下面是过程

假设每种拆分方案中，最小的数为w，则按照w的不同，我们可以把拆分方案分成2类：

第一类： w=1，我们把1除去，则剩余部分正好是数字n-1拆分成k-1部分，一共有dp[i-1][k-1]个；

第二类： w>1，则所有的数都>1，我们把所有的数-1，则正好减掉了k个数，情况变成了数字n-k拆分成k部分，一共有dp[n-k][k]个。根据加法原理，得出DP方程。

DP方程： dp[n][k]=dp[n-1][k-1]+dp[n-k][k]

如果找到了方程

就很简单

否则

就是害人

下面是代码

加油！

大家最爱的代码

#include<bits/stdc++.h>

#include<iostream>

#include<cstdlib>

#include<cstdio>

using namespace std;

int sum,n,dp[1001][1001];

int main()

{

memset(dp,0,sizeof(dp));

cin>>n;

for(int i=1;i<=n;i++) dp[i][1]=1;

for(int i=2;i<=n;i++)

for(int j=2;j<=i;j++)

dp[i][j]=dp[i-1][j-1]+dp[i-j][j];

for(int j=2;j<=n;j++)

sum+=dp[n][j];

cout<<sum<<endl;

return 0;

}

加油！

萌二宝来了

加油

往期精彩推荐

本文合肥一六八中学校园图片

来自老爸学校的张尚镯伯伯

在此表示感谢

欢迎关注

亮星的信息学小屋

觉得有用，请点右下方“在看”，谢谢鼓励

vlambda博客
学习文章列表