試題 算法訓練 印章

這個就是csdn我寫的，轉到博客園里面

動態規劃：

資源限制

時間限制：1.0s 內存限制：256.0MB

問題描述

　　共有n種圖案的印章，每種圖案的出現概率相同。小A買了m張印章，求小A集齊n種印章的概率。

輸入格式

　　一行兩個正整數n和m

輸出格式

　　一個實數P表示答案，保留4位小數。

樣例輸入

2 3

樣例輸出

0.7500

數據規模和約定

　　1≤n，m≤20

題目意思簡潔明了。。。。

動態規劃：

1.設置狀態（看是一維數組還是二維數組，一般的題目都是二維數組，經驗之談）

2.找狀態之間的關系，

3.寫代碼

這其中1,2是最難的，首先把狀態想出來這一步就可以勸退很多人了，怎么想狀態呢，把我平時做dp的思路跟你們說一下：

首先看題目，有買的印章數和印章總數兩個變量，就自然而然地想成二維數組dp[i] [j]，數組有了。狀態呢？題目要求的是概率嘛，那我們dp數組的值就是概率。那么，i，j怎么說呢？題目說了小A買了m張，要湊齊n種，那么我們就設：dp[i] [j]表示買 i 張湊齊 j 種印章的概率。

這樣，狀態就大致想出來了！（為什么是大致？因為不確定我們的思路是不是對的，狀態是根據題意、經驗和感覺設想出來的），可能就是要多做吧。

狀態設想出來，二維數組的表格先畫出來（如上圖）。然后尋找初始狀態（一般都是i == 1,2,3或者j == 1,2,3這種i，j的值很小的）。

題目中有 n 種印章, 每種概率是 1/n;

先來看i<j的時候：因為買 i 張最多只能湊齊 i 種，所以這種情況概率為0

再來看j=1的時候：

i=1：dp[i] [1]表示的意思是買 i 張湊齊 1 種的概率，很明顯 i == 1 && j == 1 的時候dp[1] [1] = 1，因為你買一張是無論如何都可以湊齊一種的，是吧。

i > 1：i > 1 && j == 1. 意思就是買 i 張湊齊 1 種印章的概率，意味著買的這 i 張印章是同一種，概率就是 (1/n)^i，但是，我們這 i 張要么是第一種，要么是第二種......( 要么是第k種 ，1 <= k <= n )。最后還要乘上n，所以這個情況 dp[i] [j] = (1/n)^(i-1)

初始狀態大致就上面這些了：↑

最后來看中間的狀態 dp[i] [j]：

我們買的第 i 張，有兩種狀態，一：跟前面買的 i-1 張中有重復的 二：跟前面買的 i-1 張中沒有重復的

什么意思呢？ 比如：(總共有5種印章，標號1,2,3,4,5) 我正在買第5張，前面四張湊齊了1,2,3,4號，那么第5張如果也是1,2,3,4號中的一個就表示重復的；如果第5張是5號，就表示沒有重復的。

一：有重復的：就表明前面買的 i-1 張，已經湊齊了 j 種。dp[i] [j] = dp[i-1] [j] * ( j / n ); j/n是什么意思？

二：無重復的

前面買的 i-1 張 湊齊了 j-1 種， 我們買的第 i 張與前面的不重復，就又湊齊了一種：

dp[i] [j] = dp[i-1] [j-1] * (n-j+1) / n;

然后把兩種情況加起來就是dp[i] [j] 的概率了?。?/p>

#include <iostream>
#include <cmath>
using namespace std;
double dp[25][25], p;
int main()
{
	
    //記住是小數啊，要*1.0進行類型轉換的
	int n, m;
	cin >> n >> m;
	p = 1.0 / n; //每種出現的概率
	
	for ( int i = 1; i <= m; ++i ) {
		for ( int j = 1; j <= n; ++j ) {
			if ( i <  j ) dp[i][j] = 0;
			if ( j == 1 ) {
				dp[i][j] = pow (p, i-1);  //p^(i-1)
			}
			else {
				dp[i][j] = dp[i-1][j] * (j*1.0/n) + dp[i-1][j-1] * ((n-j+1)*1.0/n);
			}
		}
	}
//	cout << "dp\n";
//		for ( int i = 1; i <= m; ++i ) {
//		for ( int j = 1; j <= n; ++j ) {
//			printf("%.2lf  ",dp[i][j]);
//		}
//		cout << endl;
//	}
	
	printf("%.4lf  ",dp[m][n]);
	return 0;
}

總結：

1.數組確定（一維，還是二維，三維，n維也有....一般沒有）

2.數組值（題目求什么，我們數組表示的值一般就是什么）

3.狀態設想 （dp[i] [j]表示 什么什么 i 什么什么 的時候， 什么什么 j 什么什么的時候 的 值）

4.初始狀態（就是找特殊值，i=1,2,3 j=1,2,3）

5.中間狀態 （ i, j 與 i-1, i-2, j-1, j-2......）

6.寫代碼