算法訓(xùn)練 數(shù)的劃分 ?

時(shí)間限制：1.0s ? 內(nèi)存限制：256.0MB

??????

問題描述

　　將整數(shù)n分成k份，且每份不能為空，任意兩份不能相同(不考慮順序)。
　　例如：n=7，k=3，下面三種分法被認(rèn)為是相同的。
　　1，1，5; 1，5，1; 5，1，1;
　　問有多少種不同的分法。

輸入格式

　　n，k

輸出格式

　　一個(gè)整數(shù)，即不同的分法

樣例輸入

7 3

樣例輸出

4 {四種分法為：1，1，5;1，2，4;1，3，3;2，2，3;}

數(shù)據(jù)規(guī)模和約定

　　6<n<=200，2<=k<=6

?

#include<iostream> using namespace std; int dp[210][16]; int main() {int n,k;cin>>n>>k;for(int i=1;i<=n;i++)dp[i][1]=1;//分成一份的時(shí)候只有一種情況 for(int i=1;i<=n;i++)for(int j=2;j<=k;j++)//分成一份的時(shí)候跳過，從2開始 {if(i>=j)dp[i][j]=dp[i-j][j]+dp[i-1][j-1];/*k>n情況數(shù)肯定是0； 當(dāng) i>=j時(shí)，縮小規(guī)模，分成兩類討論：1.當(dāng)至少有一個(gè)等于一，我們便可以縮小它的規(guī)模，變成研究，dp[i-1][j-1]的情況數(shù)；2. 當(dāng)所有的都大于等于2，實(shí)際上也就等于每一份里面減去一個(gè)一，而份數(shù)不變的情況dp[i-j][j] */ }cout<<dp[n][k]<<endl; }

?

?

?

?

?

總結(jié)

以上是生活随笔為你收集整理的算法训练 数的划分 动态规划的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。