動態規劃典型題目/
00 題目
將正整數n無需拆分為最大數為k的拆分方案有多少種？
?
要求所有的拆分方案不重復，
示例：
輸入：n=5，k=5
輸出：(5,5)=7
示例分析：
-
5=5
-
5=4+1
-
5=3+2
-
5=3+1+1
-
5=2+2+1
-
5=2+1+1+1
-
5=1+1+1+1+1
所以一共七種，
01 思路
01-1 型別
求解這一問題的思路有很多，在這里是想作為動態規劃的例題進行分析，所以采用動態規劃，
01-2 演算法
使用動態規劃，最重要的是狀態轉移方程
簡單說就是當前狀態對下一狀態，依據限制條件，進行決策的函式，
來想一下，n和k的關系：
-
n=1或者k=1時，顯然 f(n,k)=1;
-
n<k時，有 f(n,k)=f(n,n);
-
n=k時，f(n,n)=f(n,n-1)+1
-
//即將k降一次的感覺，因為這種情況必有一種拆分是他自己，比如上面的5，5
-
-
n>k時，我們考慮一下，會有兩種大的情況：
-
第一種，n的拆分里有k，那這一大類其實相當于f(n,k)=f(n-k,k)
-
第二種，n的拆分里沒k，那就是拆分里所有數都比k小，即n的(k-1)的拆分，即f(n,k)=f(n,k-1);
-
02 代碼
這樣的代碼就很好實作，
典型動態規劃實作的話，就只有嵌套回圈和if-else回圈，
1 //求解n的k拆分 2 #include<stdio.h> 3 #include<string.h> 4 #define MAXN 500 5 int dp[MAXN][MAXN]; 6 void Split(int n, int k){ 7 for(int i = 1; i <= n; i++){ 8 for(int j = 1; j <= k; j++){ 9 if(i == 1 || j == 1){ 10 dp[i][j] = 1; 11 } 12 else if(i < j){ 13 dp[i][j] = dp[i][i]; 14 } 15 else if(i == j){ 16 dp[i][j] = dp[i][j-1]+1; 17 } 18 else{ 19 dp[i][j] = dp[i][j-1] + dp[i-j][j]; 20 } 21 } 22 } 23 } 24 int main(){ 25 int n=5,k=5; 26 memset(dp, 0, sizeof(dp)); 27 Split(n,k); 28 printf("(%d, %d)=%d",n,k,dp[n][k]); 29 return 0; 30 } 31
因為這個問題是遞回的，所以可以采用遞回來寫，解決程序是自頂向下的，當然就在遞回程序中將算過的子問題放進dp陣列，在后續dp不等0時就是此前已經算過了，直接return就行，
這種方法也叫備忘錄法
1 #include<stdio.h> 2 #include<string.h> 3 #define MAXN 500 4 int dp[MAXN][MAXN]; 5 int dpf(int n, int k){ 6 if(dp[n][k] != 0)return dp[n][k]; 7 if(n == 1 || k == 1){ 8 dp[n][k] = 1; 9 return dp[n][k]; 10 } 11 else if(n < k){ 12 dp[n][k] = dpf(n, n); 13 return dp[n][k]; 14 } 15 else if(n == k){ 16 dp[n][k] = dpf(n, k-1)+1; 17 return dp[n][k]; 18 } 19 else{ 20 dp[n][k] = dpf(n, k-1)+dpf(n-k, k); 21 return dp[n][k]; 22 } 23 } 24 int main(){ 25 int n=5,k=5; 26 memset(dp, 0, sizeof(dp)); 27 printf("(%d, %d)=%d",n,k,dpf(n,k)); 28 return 0; 29 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/347015.html
標籤：其他