数的划分
解题思路
这道题可以用dp也可以用dfs做,因为这道题目的数据范围很小。
我们用$ dp[i][j] $表示将i划分成j份的可能数
我们将状态转移方程列为
dp[i][j]=dp[i-j][1]+dp[i-j][2]+……+dp[i-j][j-1]+dp[i-j][j];
但由于这是O(n^3)算法,我们要试着给它降一维。
因为
dp[i-1][j-1]=dp[(i-1)-(j-1)][1]+dp[(i-1)-(j-1)][2]+……+dp[(i-1)-(j-1)][j-1];
所以等量代换之后,可得
dp[i][j]=dp[i-1][j-1]+dp[i-j][j];
当列出状态转移方程之后可以试着解方程到最简形式。
代码
代码很短,就十几行。
#include<iostream>
using namespace std;
int dp[1005][10];
int n,k;
int main(){
cin>>n>>k;
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
if(i>=j){
dp[i][j]=dp[i-j][j]+dp[i-1][j-1];
}
}
}
cout<<dp[n][k];
return 0;
}
本文链接:https://kaispace.com.cn/index.php/archives/387/
如果未注明出处,复制公开后需将注明本博客链接。打赏作者