動態規劃基礎水題提綱

提綱

漢諾塔

漢諾塔：漢諾塔（又稱河內塔）問題是源于印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

動態規劃：

1) 問題具有最優子結構性質。如果問題的最優解所包含的 子問題的解也是最優的，我們就稱該問題具有最優子結 構性質。

2) 無后效性。當前的若干個狀態值一旦確定，則此后過程 的演變就只和這若干個狀態的值有關，和之前是采取哪 種手段或經過哪條路徑演變到當前的這若干個狀態，沒 有關系。

例子：

7

3 ? ?8

8 ? ?1 ? ?0

2 ? ?7 ? ?4 ? ?4

4 ? ?5 ? 2 ? 6 ? ? 5

在上面的數字三角形中尋找一條從頂部到底邊的路徑，使得 路徑上所經過的數字之和最大。路徑上的每一步都只能往左下或 右下走。只需要求出這個最大和即可，不必給出具體路徑。

---------------------

把原問題分解為若干個子問題，子問題和原問題形式相同 或類似，只不過規模變小了。子問題都解決，原問題即解決(數字三角形例）。

1）有一只兔子，從出生后第2個月起每個月都生一只兔子，小兔子長到第2個月后每個月又生一只兔子，假如兔子都不死，問每個月的兔子總數為多少？

2）有一只兔子，從出生后第3個月起每個月都生一只兔子，小兔子長到第三個月后每個月又生一只兔子，假如兔子都不死，問每個月的兔子總數為多少？

3）有一頭母牛，它每年年初生一頭小母牛。每頭小母牛從第四個年頭開始，每年年初也生一頭小母牛。請編程實現在第n年的時候，共有多少頭母牛？

4）我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個2*1的小矩形無重疊地覆蓋一個2*n的大矩形，總共有多少種方法？

一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法（先后次序不同算不同的結果）。

6）一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。

7）有一個X*Y的網格，小團要在此網格上從左上角到右下角，只能走格點且只能向右或向下走。請設計一個算法，計算小團有多少種走法。給定兩個正整數int x,int y，請返回小團的走法數目。

推薦讀物:

背包問題

背包九講

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。