Problem : 三只小豬
Description
這日弯予，快碼佳編四兄弟姐妹來到了一個山腳下棺克，只聽一個老奶奶給兩個孫子講故事辙培。
你聽說過三只小豬的故事嗎？這是一個經(jīng)典的故事啥箭。很久很久以前，有三只小豬治宣。第一只小豬用稻草建的房子急侥，第二個小豬用木棍建的房子，第三個小豬則使用磚做為材料侮邀。一只大灰狼想吃掉它們并吹倒了稻草和木棍建的房子坏怪。但是磚蓋的房子很結(jié)實，狼最終也沒有破壞掉豌拙，最后小豬們戰(zhàn)勝了大灰狼并把它尾巴燒掉了陕悬。
為了自己的安全，小豬們又建造了一個新磚房按傅。但是現(xiàn)在問題出現(xiàn)了捉超，怎樣把三個小豬分配到兩個房子里呢胧卤？第三只小豬是三只小豬中最聰明的一只，為了不浪費任何一個房子拼岳，它總共考慮了三種方案枝誊，如下圖
[圖片上傳失敗...(image-1e2add-1635653105532)]
但是將來怎么辦呢？”第三只小豬知道將來隨著成員的增多惜纸，它們將會蓋更多的房子叶撒。它想知道給定了房子和豬的數(shù)目后，房子的分配方案有多少耐版，但這個問題對于它來說祠够，很明顯有點難了，你能幫小豬解決這個問題嗎粪牲？
Input
多組測試古瓤，每組 僅有一行，包含兩個整數(shù)n和m腺阳，分別表示小豬的數(shù)目和房間數(shù)（1≤n≤20落君，0≤m≤20）
Output
每組輸出一行，僅一個整數(shù)亭引，表示將n只小豬安置在m個房間且沒有房間空閑的方案數(shù)绎速。
Sample Input
4 2
Sample Output
7
思路：
n只小豬放到m房子，不允許有空房子焙蚓，
這里纹冤，我們用 dp[m][n] 來表示情況總數(shù)
首先我們可以直接想出這么幾種情況：
1.如果過m>n,肯定有空房子，那么 就是0種情況主届。
2.如果m=n赵哲，那么每一只小豬肯定都要分配到不同房子 就是1種情況。
3.如果m=1君丁，而且n>0枫夺，那么，所有小豬都在一個房子绘闷，也是1種情況 展示代碼如下：
for(int i=1;i<=n;i++)//一個房間小豬分配的情況
dp[1][i]=1;
現(xiàn)在橡庞，特殊的情況知道了，那么印蔗，我們想一般的情況扒最；
我們按照提示的圖來分析下： n=3，m=2华嘹；情況數(shù)目為dp[2][3]
三只小豬 x1吧趣，x2，x3；
有這么三種情況：
x1 x2 | x3
x1 x3 | x2
x2 x3 | x1
此時dp[3][2]=3
那么 如果 再來一只小豬x4呢（在房子數(shù)目不變情況下）
首先 針對x1 x2 | x3 這種情況 x4 可以插入到2個房子（m個房子）中去
然后和x1 x2 | x3 并列的情況有三種
那么此時dp[2][4]=2dp[2][3]*
即dp[2][4]=2dp[2][4-1]*
但是除此之外强挫，x4也可能單獨一個房間岔霸，此時的情況是原先三只小豬分配到1個房子 dp[1][3]
即dp[2-1][4-1]
歸納總結(jié)可以得出狀態(tài)轉(zhuǎn)移方程
dp[m][n] = dp[m][n-1]*m + dp[m-1][n-1]
代碼
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long dp[25][25];
int m,n;
while(cin>>n>>m)
{
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)//一個房間小豬分配；
dp[1][i]=1;
for(int i=2;i<=m;i++)//m個房間
for(int j=1;j<=n;j++)//n只小豬分配
dp[i][j]=dp[i][j-1]*i+dp[i-1][j-1];
cout<<dp[m][n]<<endl;
}
return 0;
}
