點擊打開鏈接

把 M個同樣的蘋果放在 N個同樣的盤子里，允許有的盤子空著不放

問共有多少種方法？5，1，1和1，5，1是同一種方法?

解法一：

poj 1664 放蘋果 DP

dp[i][j]表示共 i個蘋果放入 j個盤子里的方法
狀態轉移過程：

1.這 j個盤子有空盤子，這時候i個蘋果放入j個盤子的方法，
和i個蘋果放入j-1個盤子的方法是一樣的

2.j個盤子中沒有空盤子，那么可以從每個盤子中移除一個，

原問題轉換成i-j個蘋果放到 j個盤子里?

3.為什么沒有空盤子時，蘋果只拿走一個？

這個問題我們可以這樣想，假設放置最少的盤子中有k個蘋果，
那么這個狀態可以唯一地，由連續k次每次從每個盤子中拿走一個蘋果而得到，
所以就不會出現重復的子狀態，也就滿足了題目的顯示條件！


#include<iostream> #include<cstring> using namespace std; const int MAXN=15; int dp[MAXN][MAXN]; int M,N;int main() {ios::sync_with_stdio(false);int t;cin>>t;while(t--){cin>>M>>N;memset(dp,-1,sizeof(dp));for(int i=1;i<=10;i++)dp[0][i]=dp[1][i]=dp[i][1]=1;//邊界條件for(int i=1;i<=10;i++){for(int j=1;j<=10;j++){if(dp[i][j]==-1){if(i<j)//證明有空盤子dp[i][j]=dp[i][j-1];else//沒有空盤子，就先給這 j個盤子每個都放一個蘋果，dp[i][j]=dp[i][j-1]+dp[i-j][j]; }}}cout<<dp[M][N]<<endl; }return 0;}

解法二：

DFS遞歸搜索

一、遞歸邊界

只有一個盤子，無論有多少個蘋果都只有一種方法 二、遞歸過程 //第一：如果盤子的個數大于蘋果的個數，就把m個蘋果放到m個盤子的方法 //第二： //1.將至少其中一個盤子不放，那么就是 m個蘋果放到n-1個盤子的方法 //2.每個盤子放一個，然后就是 m-n個蘋果放到n個盤子里 #include<iostream> using namespace std;int apple_divide(int m,int n) { //只有一個盤子，無論有多少個蘋果都只有一種方法 if(m==0||n==1)return 1;if(n>m)//如果盤子的個數大于蘋果的個數return apple_divide(m,m);//m個蘋果放到m個盤子的方法 elsereturn apple_divide(m,n-1)+apple_divide(m-n,n); //1.將至少其中一個盤子不放，那么就是 m個蘋果放到n-1個盤子的方法 //2.每個盤子放一個，然后就是 m-n個蘋果放到n個盤子里 } int main() {ios::sync_with_stdio(false); int m,n,k;//m個蘋果，n個盤子 cin>>k;while(k--){cin>>m>>n;cout<<apple_divide(m,n)<<endl;}return 0;}

總結

以上是生活随笔為你收集整理的poj 1664 放苹果 DPDFS的全部內容，希望文章能夠幫你解決所遇到的問題。

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