?

問題描述

　　一個正整數可以劃分為多個正整數的和，比如n=3時：
　　3；1＋2；1＋1＋1；
　　共有三種劃分方法。
　　給出一個正整數，問有多少種劃分方法。

輸入格式

　　一個正整數n

輸出格式

　　一個正整數，表示劃分方案數

樣例輸入

3

樣例輸出

3

數據規模和約定

　　n<=100

?

#include<iostream> using namespace std; int dp[110][110];//dp[i][j]用來表示，數值i分成的數最高不超過j的情況數 int main() {int n;cin>>n;for(int i=0;i<=n;i++){dp[i][1]=1;//拆出來的數不大于1的情況只有一種 dp[0][i]=1;//0只有本身一種情況，因為dp[0][N]=dp[0][0],很玄學，哈哈 }for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(j<=i){dp[i][j]=dp[i][j-1]+dp[i-j][j];/*dp[n][m]表示整數 n 的劃分中，每個數不大于 m 的劃分數。則劃分數可以分為兩種情況:a. 劃分中每個數都小于 m， 相當于每個數不大于 m- 1, 故劃分數為 dp[n][m-1].b. 劃分中有一個數為 m. 那就在 n中減去 m , 剩下的就相當于把 n-m 進行劃分， 故劃分數為 dp[n-m][m];*/}else{dp[i][j]=dp[i][i];//如果允許拆出來的最大的數比這個數本身還大，那么最大的數也就是這個數本身 }// cout<<"dp["<<i<<"]["<<j<<"]="<<dp[i][j]<<endl;}cout<<dp[n][n]<<endl;}

另外感謝小伙伴給我的幫助

?

?

?

?

總結

以上是生活随笔為你收集整理的算法提高 数的划分 动态规划 无序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。