題目

https://leetcode.com/problems/guess-number-higher-or-lower-ii/

題解

首先，看了 Related Topics，知道這是個(gè) dp 問題。

動(dòng)態(tài)規(guī)劃思路總結(jié)

根據(jù) dp 的常規(guī)流程，先選幾個(gè) 計(jì)算量較小 的輸入，手動(dòng)嘗試一下，找感覺。

然后 逐漸擴(kuò)大 輸入的數(shù)，發(fā)現(xiàn) 計(jì)算量劇增，手動(dòng)計(jì)算已經(jīng)很難列出所有情況了。出現(xiàn)這種現(xiàn)象大多數(shù)是因?yàn)?#xff0c;你的嘗試的過程，實(shí)際上是 將遞歸暴力展開 的過程。

展開的項(xiàng)數(shù)多了之后，你會(huì)隱隱約約的感覺到：有些部分被重復(fù)計(jì)算了！

然后，你要 讓這種模糊的感覺變得清晰（我稱之為玄學(xué)…）。因?yàn)檫@就是使用 dp 的目的：存儲(chǔ)已經(jīng)計(jì)算過的狀態(tài)，避免重復(fù)計(jì)算。

讓模糊的感覺變清晰的過程，就是把 遞歸變成 dp 的過程，具體方法可以是：寫出遞歸需要的參數(shù)，分別將這些參數(shù)作為 dp 數(shù)組的維度，dp 存儲(chǔ)值的就是題目要求解的值。

這樣你就 設(shè)計(jì)出了 dp 數(shù)組。先把 dp 數(shù)組的 默認(rèn)值、初始值 填好，再看看 還有那些容易計(jì)算的數(shù)，依次計(jì)算 它們（不一定是從左到右。還可能是上下相關(guān)，可能是斜向，也可能是像累加和那樣的索引下標(biāo)訪問）。你在這個(gè)過程中填充 dp 數(shù)組的順序，就是用代碼實(shí)現(xiàn)時(shí)填充 dp 數(shù)組的順序。

填完 dp 數(shù)組之后，答案就呼之欲出了。剩下的就是對 dp 數(shù)組的空間優(yōu)化，這里不再詳述。

附上做這題的草稿，大概就是上述的嘗試過程。

class Solution {public int getMoneyAmount(int n) {int[][] dp = new int[n + 2][n + 2]; // 二維表示左右邊界, 用n+2作為冗余0可省略越界判斷for (int i = 2; i <= n; i++) { // dp[L][R] 當(dāng)L=R時(shí)值為0，可以直接從i=2開始for (int j = i; j <= n; j++) { int L = j - i + 1;int R = j;int min = Integer.MAX_VALUE;for (int M = L; M <= R; M++) { // M從L到R，找到所有M情況下的min// [L...M-1] + M + [M+1...R]min = Math.min(min, Math.max(dp[L][M - 1], dp[M + 1][R]) + M);}dp[L][R] = min;}}return dp[1][n];} }

總結(jié)

以上是生活随笔為你收集整理的leetcode 375. Guess Number Higher or Lower II | 375. 猜数字大小 II（动态规划思路总结）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。