動態規划算法幫我通關了「魔塔」

2021-01-15 馬家軍談Java

讀完本文,可以去力扣解決如下題目:174.地下城遊戲(Hard)

「魔塔」是一款經典的地牢類遊戲,碰怪物要掉血,吃血瓶能加血,你要收集鑰匙,一層一層上樓,最後救出美麗的公主。

現在手機上仍然可以玩這個遊戲:

嗯,相信這款遊戲承包了不少人的童年回憶,記得小時候,一個人拿著遊戲機玩,兩三個人圍在左右指手畫腳,這導致玩遊戲的人體驗極差,而左右的人異常快樂

力扣第 174 題是一道類似的題目,我簡單描述一下:

輸入一個存儲著整數的二維數組grid,如果grid[i][j] > 0,說明這個格子裝著血瓶,經過它可以增加對應的生命值;如果grid[i][j] == 0,則這是一個空格子,經過它不會發生任何事情;如果grid[i][j] < 0,說明這個格子有怪物,經過它會損失對應的生命值。

現在你是一名騎士,將會出現在最上角,公主被困在最右下角,你只能向右和向下移動,請問騎士的初始生命值至少為多少,才能成功救出公主?

換句話說,就是問你至少需要多少初始生命值,能夠讓騎士從最左上角移動到最右下角,且任何時候生命值都要大於 0。

函數籤名如下:

int calculateMinimumHP(int[][] grid);比如題目給我們舉的例子,輸入如下一個二維數組grid,用K表示騎士,用P表示公主:

算法應該返回 7,也就是說騎士的初始生命值至少為 7 時才能成功救出公主,行進路線如圖中的箭頭所示。

上篇文章 最小路徑和 寫過類似的問題,問你從左上角到右下角的最小路徑和是多少。

我們做算法題一定要嘗試舉一反三,感覺今天這道題和最小路徑和有點關係對吧?

想要最小化騎士的初始生命值,是不是意味著要最大化騎士行進路線上的血瓶?是不是相當於求「最大路徑和」?是不是可以直接套用計算「最小路徑和」的思路?

但是稍加思考,發現這個推論並不成立,吃到最多的血瓶,並不一定就能獲得最小的初始生命值。

比如如下這種情況,如果想要吃到最多的血瓶獲得「最大路徑和」,應該按照下圖箭頭所示的路徑,初始生命值需要 11:

但也很容易看到,正確的答案應該是下圖箭頭所示的路徑,初始生命值只需要 1:

所以,關鍵不在於吃最多的血瓶,而是在於如何損失最少的生命值。

這類求最值的問題,肯定要藉助動態規劃技巧,要合理設計dp數組/函數的定義。類比前文 最小路徑和問題,dp函數籤名肯定長這樣:

int dp(int[][] grid, int i, int j);但是這道題對dp函數的定義比較有意思,按照常理,這個dp函數的定義應該是:

從左上角(grid[0][0])走到grid[i][j]至少需要dp(grid, i, j)的生命值。

這樣定義的話,base case 就是i, j都等於 0 的時候,我們可以這樣寫代碼:

int calculateMinimumHP(int[][] grid) { int m = grid.length; int n = grid[0].length; // 我們想計算左上角到右下角所需的最小生命值 return dp(grid, m - 1, n - 1);}int dp(int[][] grid, int i, int j) { // base case if (i == 0 && j == 0) { // 保證騎士落地不死就行了 return gird[i][j] > 0 ? 1 : -grid[i][j] + 1; } ...}PS:為了簡潔,之後dp(grid, i, j)就簡寫為dp(i, j),大家理解就好。

接下來我們需要找狀態轉移了,還記得如何找狀態轉移方程嗎?我們這樣定義dp函數能否正確進行狀態轉移呢?

我們希望dp(i, j)能夠通過dp(i-1, j)和dp(i, j-1)推導出來,這樣就能不斷逼近 base case,也就能夠正確進行狀態轉移。

具體來說,「到達A的最小生命值」應該能夠由「到達B的最小生命值」和「到達C的最小生命值」推導出來:

但問題是,能推出來麼?實際上是不能的。

因為按照dp函數的定義,你只知道「能夠從左上角到達B的最小生命值」,但並不知道「到達B時的生命值」。

「到達B時的生命值」是進行狀態轉移的必要參考,我給你舉個例子你就明白了,假設下圖這種情況:

你說這種情況下,騎士救公主的最優路線是什麼?

顯然是按照圖中藍色的線走到B,最後走到A對吧,這樣初始血量只需要 1 就可以;如果走黃色箭頭這條路,先走到C然後走到A,初始血量至少需要 6。

為什麼會這樣呢?騎士走到B和C的最少初始血量都是 1,為什麼最後是從B走到A,而不是從C走到A呢?

因為騎士走到B的時候生命值為 11,而走到C的時候生命值依然是 1。

如果騎士執意要通過C走到A,那麼初始血量必須加到 6 點才行;而如果通過B走到A,初始血量為 1 就夠了,因為路上吃到血瓶了,生命值足夠抗A上面怪物的傷害。

這下應該說的很清楚了,再回顧我們對dp函數的定義,上圖的情況,算法只知道dp(1, 2) = dp(2, 1) = 1,都是一樣的,怎麼做出正確的決策,計算出dp(2, 2)呢?

所以說,我們之前對dp數組的定義是錯誤的,信息量不足,算法無法做出正確的狀態轉移。

正確的做法需要反向思考,依然是如下的dp函數:

int dp(int[][] grid, int i, int j);但是我們要修改dp函數的定義:

從grid[i][j]到達終點(右下角)所需的最少生命值是dp(grid, i, j)。

那麼可以這樣寫代碼:

int calculateMinimumHP(int[][] grid) { // 我們想計算左上角到右下角所需的最小生命值 return dp(grid, 0, 0);}int dp(int[][] grid, int i, int j) { int m = grid.length; int n = grid[0].length; // base case if (i == m - 1 && j == n - 1) { return grid[i][j] >= 0 ? 1 : -grid[i][j] + 1; } ...}根據新的dp函數定義和 base case,我們想求dp(0, 0),那就應該試圖通過dp(i, j+1)和dp(i+1, j)推導出dp(i, j),這樣才能不斷逼近 base case,正確進行狀態轉移。

具體來說,「從A到達右下角的最少生命值」應該由「從B到達右下角的最少生命值」和「從C到達右下角的最少生命值」推導出來:

能不能推導出來呢?這次是可以的,假設dp(0, 1) = 5, dp(1, 0) = 4,那麼可以肯定要從A走向C,因為 4 小於 5 嘛。

那麼怎麼推出dp(0, 0)是多少呢?

假設A的值為 1,既然知道下一步要往C走,且dp(1, 0) = 4意味著走到grid[1][0]的時候至少要有 4 點生命值,那麼就可以確定騎士出現在A點時需要 4 - 1 = 3 點初始生命值,對吧。

那如果A的值為 10,落地就能撿到一個大血瓶,超出了後續需求,4 - 10 = -6 意味著騎士的初始生命值為負數,這顯然不可以,騎士的生命值小於 1 就掛了,所以這種情況下騎士的初始生命值應該是 1。

綜上,狀態轉移方程已經推出來了:

int res = min( dp(i + 1, j), dp(i, j + 1)) - grid[i][j];dp(i, j) = res <= 0 ? 1 : res;根據這個核心邏輯,加一個備忘錄消除重疊子問題,就可以直接寫出最終的代碼了:

/* 主函數 */int calculateMinimumHP(int[][] grid) { int m = grid.length; int n = grid[0].length; // 備忘錄中都初始化為 -1 memo = new int[m][n]; for (int[] row : memo) { Arrays.fill(row, -1); } return dp(grid, 0, 0);}// 備忘錄,消除重疊子問題int[][] memo;/* 定義:從 (i, j) 到達右下角,需要的初始血量至少是多少 */int dp(int[][] grid, int i, int j) { int m = grid.length; int n = grid[0].length; // base case if (i == m - 1 && j == n - 1) { return grid[i][j] >= 0 ? 1 : -grid[i][j] + 1; } if (i == m || j == n) { return Integer.MAX_VALUE; } // 避免重複計算 if (memo[i][j] != -1) { return memo[i][j]; } // 狀態轉移邏輯 int res = Math.min( dp(grid, i, j + 1), dp(grid, i + 1, j) ) - grid[i][j]; // 騎士的生命值至少為 1 memo[i][j] = res <= 0 ? 1 : res; return memo[i][j];}這就是自頂向下帶備忘錄的動態規劃解法,參考前文 動態規劃套路詳解 很容易就可以改寫成dp數組的迭代解法,這裡就不寫了,讀者可以嘗試自己寫一寫。

這道題的核心是定義dp函數,找到正確的狀態轉移方程,從而計算出正確的答案。

來源:https://mp.weixin.qq.com/s/KD5sS_wbwiWH0rObuya7aA

相關焦點

  • 如何掌握動態規划算法的套路?
    動態規劃(Dynamic Programming),簡稱DP,這個名字給人的感覺是一種非常高大上非常複雜的算法,很多同學看到這個名字可能就會望而卻步,在面試的時候也非常害怕被問到動態規劃的題目。實際上,它並不是不是一種確定的算法,它是一種最優化的方法求解問題的思想或方法。它是由美國數學家貝爾曼(Bellman)在研究多階段決策過程的優化問題時提出。不過,與之對應的還有一些與時間無關的靜態規劃,如:線性規劃、非線性規劃等。在運籌學中,動態規劃是的非常重要的內容,在各個行業領域都有著廣泛的應用。我們如何理解動態規劃?
  • 計算機五大算法之三,動態規劃
    與分治法不同的是,動態規劃求解的問題,子問題往往不是相互獨立的,若用分治法解這類問題,分解得到的子問題太多,有些子問題,重複計算很多次。如果能保存已解決子問題的解,需要時找出已求解的解,就可以避免大量重複計算,所以可以用一個表來記錄已求解子問題的解,這就是動態規劃的基本思路。二、適用情況和基本特徵適用動態規划算法必須滿足最優化原理、無後效性和子問題重疊性1.
  • 動態規划算法Dynamic Programming
    動態規劃與分治法相似,都是通過組合子問題的解來求解原問題。不同的是,分治法將問題劃分為互不相交的子問題,遞歸的求解子問題,再將他們的解組合起來,求出原問題的解。與之相反,動態規劃應用於子問題重疊的情況,即不同的子問題具有公共的子子問題。在這種情況下,分治法會做許多不必要的工作,他會反覆求解那些公共子子問題。
  • 動態規划算法入門,這就夠了
    動態規劃(Dynamic programming,簡稱DP),是大家都覺得比較難以掌握的算法。為了應付面試,我們經常會背誦一下斐波那楔數列或者背包問題的源碼,其實,只要理解了思想,掌握基本的模型,然後再來點寫代碼的套路,動態規劃並沒有那麼難。
  • 拒絕遺忘:高效的動態規划算法
    不懂動態規劃的人會在解決過的問題上再次浪費時間,懂的人則會事半功倍。那麼什麼是動態規劃?這種算法有何神奇之處?本文作者給出了初步的解答。假設你正在使用適當的輸入數據進行一些計算。你在每個實例中都進行了一些計算,以便得到一些結果。當你提供相同的輸入時,你不知道會有相同的輸出。這就像你在重新計算之前已經計算好的特定結果一樣。那麼問題出在哪裡呢?
  • 還在看算法的朋友,你需要一篇:動態規劃
    前言最近有小夥伴在後臺留言說,可不可以聊一聊動態規劃。這是一個有趣的話題,因為對於大部分業務型公司來說,面試中的算法部分並不會考這一塊。但是BAT等一線網際網路公司又不一定不會考,比如我在面試頭條的時候就被問了一道動態規劃的題目。此外,我個人覺得動態規劃有趣的原因是,我認為應用層的工程師能接觸到或者用到的「最需要思考」的算法題目了。
  • 如何掌握動態規划算法的套路? - 51CTO.COM
    動態規劃(Dynamic Programming),簡稱DP,這個名字給人的感覺是一種非常高大上非常複雜的算法,很多同學看到這個名字可能就會望而卻步,在面試的時候也非常害怕被問到動態規劃的題目。實際上,它並不是不是一種確定的算法,它是一種最優化的方法求解問題的思想或方法。它是由美國數學家貝爾曼(Bellman)在研究多階段決策過程的優化問題時提出。不過,與之對應的還有一些與時間無關的靜態規劃,如:線性規劃、非線性規劃等。在運籌學中,動態規劃是的非常重要的內容,在各個行業領域都有著廣泛的應用。我們如何理解動態規劃?
  • Java動態規划算法策略
    Dynamic Programming是五大常用算法策略之一,簡稱DP,譯作中文是「動態規劃」,可就是這個聽起來高大上的翻譯坑苦了無數人,因為看完這個算法你可能會覺得和動態規劃根本沒太大關係,它對「動態」和「規劃」都沒有太深的體現。
  • 豁然開朗經典算法之「動態規劃」
    《算法導論》是這樣解釋動態規劃的:動態規劃與分治法相似,都是通過組合子問題的解來求解原問題答案,將問題劃分為互不相交的子問題,遞歸的求解子問題,最後合併子問題的答案,得到原問題的答案。翻譯成人話就是:計算並存儲小問題的解,並將這些解組合成大問題的解。
  • 魔塔50層通關全攻略 圖文通關流程一覽
    《魔塔50層》一共有50關,很多玩家沒有辦法順利通關,今天小編就為大家帶來了魔塔50層通關全攻略!各位小夥伴千萬不要錯過呀!
  • 才不是童話魔塔35層低配攻略 魔塔35層平民通關打法技巧
    在才不是童話手遊中魔塔35層究竟該如何低配過關呢?在才不是童話手遊中魔塔35層的通關技巧可以說是不少玩家一直都想了解的呢!那麼不清楚的話下面就來看一下吧!才不是童話魔塔35層低配攻略  陣容推薦(按上陣順序):40級二星燈神,20級一星深淵白雪(核心控制),60級二星小飛俠(核心輸出),60級二星睡美人。  推薦上陣原因:燈神先手破盾,給小飛俠創造輸出環境,由於自身不需要打輸出,所以要求不高。
  • 快速搞定動態規劃
    概念:動態規劃(dynamic programming)是運籌學的一個分支,是求解決策過程(decision process)最優化的數學方法。這就是動態規劃法的基本思路。具體的動態規划算法多種多樣,但它們具有相同的填表格式。動態規劃的三特性:1.最優子結構性質:不論過去狀態和決策如何,對前面的決策所形成的狀態而言,餘下的諸決策必須構成最優策略。簡而言之,一個最優化策略的子策略總是最優的。一個問題滿足最優化原理又稱其具有最優子結構性質。
  • 算法之動態規劃實戰
    動態規劃是一種在數學,計算機科學及經濟學中使用的,通過把原問題分解為相對簡單的子問題的方式求解複雜問題的方法。動態規劃背後的思想非常簡單,基本思想是這樣的,給定一個要求解的問題,我們需要解其不同部分也就是子問題,然後在把這些子問題進行合併,最後得到原問題的解。
  • 《魔塔50層》第41層到50層怎麼過 第41層到50層通關攻略
    導 讀 魔塔50層是非常燒腦的策略冒險遊戲,遊戲難度非常高。
  • 《魔塔50層》終極通關攻略 新手必看
    導 讀 魔塔50層怎麼玩?魔塔50層怎麼過?小編為大家分享魔塔50層攻略,希望這個魔塔50層通關技巧攻略可以幫助到大家。 第一區域(1—10層) 1。
  • 《放開那三國3》「血戰魔塔」塔防詳解 動態策略應萬變
    玩家可挑戰玩法「血戰魔塔」,在固定站位的作戰場景中抵禦源源不斷來襲的敵軍。面對全新的作戰機制,如何才能夠最大化發揮武將實力創造挑戰記錄,靈活的策略運用不可或缺。高自由度武將搭配 誰說「站樁」一成不變血戰魔塔的戰鬥場景中有多個可放置武將的位置,武將上陣後在固定的位置上進行攻擊。
  • 《魔塔50層》攻略圖解 魔塔卡BUG通關技巧匯總
    魔塔50層這個遊戲出來難度還是非常高的,以至於不卡BUG不知道怎麼打過魔王,下面九遊小編就教大家如何卡BUG通關。 首先我們卡個bug,emmmm不卡bug真不知道怎麼打死魔王,(不過居然已經有大佬不卡bug通關了,我靠,膜拜啊)但是卡了bug遊戲娛樂性就會降低很多…………開始,我們進入一直往上衝,衝上第三層,遇見魔王對話,這時關閉遊戲,然後重開讀檔,拿鑰匙然後再去第四層,再回三層回去被魔王抓一次再退出讀檔,這次往下走下去拿竹蜻蜓,然後就是一個勁的往上衝,用竹蜻蜓飛就不用碰見魔王沒啥能擋你,能不打的怪就不打
  • 放開那三國3血戰魔塔詳細介紹 血戰魔塔怎麼玩
    「血戰魔塔」的戰鬥是怎樣的? 在「血戰魔塔」玩法中,無窮無盡的傀儡大軍將從傳送門中走出,玩家據守固定的陣地,抵禦一波又一波源源不斷的敵軍。 戰鬥的位置是固定的,但武將的組合和出手的戰略是靈活的。面對如此多的敵人,如何才能更快、更多地將它們擊殺?戰場的主宰權在你手中! 「血戰魔塔」是常駐玩法嗎?
  • 《才不是童話》魔塔怎麼打
    在才不是童話手遊中魔塔究竟該怎麼打呢?在才不是童話手遊中魔塔的打法技巧可以說是不少玩家一直都想了解的呢!那麼不清楚的話下面就來看一下吧! 才不是童話魔塔打法技巧攻略 玩法背景: 美麗的愛洛公主受到黑女巫的詛咒,在15歲生日那天陷入長久的沉睡。傳說只有命中注定的勇士,才能闖過黑女巫設下的層層魔法,以真愛之吻喚醒公主。
  • 《魔塔50層》通關圖文攻略 新手必看攻略大全
    導 讀 魔塔50層怎麼玩?魔塔50層怎麼過?小編為大家分享魔塔50層攻略,希望這個魔塔50層通關技巧攻略可以幫助到大家。 第一區域(1—10層) 1。