数的划分

解题思路

这道题可以用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/

如果未注明出处，复制公开后需将注明本博客链接。
打赏作者