iT邦幫忙

3

動態規劃創意題: 拯救公主問題

嗨嗨,大家好,
今天跟大家分享一題leetcode上面很有趣的一道題

返回主頁:系列篇章統整: 好好規劃學習動態規劃(Dynamic Programming)

參考題目: 174. Dungeon Game
題意:
公主被魔王抓走了,被關在地牢中,
騎士要從地圖的左上角出發去救被關在地圖右下角的公主,
每次騎士只能往右方或下方一格行走,
並且通過每個房間時,
可能因與惡魔戰鬥減少生命值,
亦或撿到生命寶箱回復生命值,
也可能什麼事也沒發生,
如果騎士生命值小於或等於0就掛了
請問騎士最少需要多少生命值才能通關呢?

範例地圖:
https://ithelp.ithome.com.tw/upload/images/20200621/20117114MuJKYJJJgY.png

騎士要往右走兩格,往下走兩格,
最低需生命值7才能過關

思路解析

我覺得這一題是真的很創新也很難,
既不是單純求最小也不是求最大,
一開始有想到兩個思路都不行

思路一、解最大路徑和問題?

這是我一開始的想法,
動態規劃經典題: 最短路徑之和這邊不是有個最短路徑和問題嗎?
如果我改成求最大路徑和
DP[i][j] = max(DP[i-1][j], DP[i][j-1]) + grid[i][j]這樣行不行呢?
讓騎士在全局中儘量讓自己的生命值最大化,
譬如說以範例地圖來說,
https://ithelp.ithome.com.tw/upload/images/20200621/20117114MuJKYJJJgY.png

生命值最大化的路徑便是往下走兩格再往右兩格,
生命值為-2 -5 + 10 + 30 -5 = 28

但是如果走這條路的話,
騎士最低需生命值8才能過關,
否則前面踩到-2, -5就掛了,
後面拿那麼多生命值也沒用。

思路二、貪婪的選擇最小傷害路線?

這是我第二個想法,
再以範例地圖來說,
https://ithelp.ithome.com.tw/upload/images/20200621/20117114MuJKYJJJgY.png

一開始我站在-2的位置,看一下下一步的最小傷害,
-3的傷害比-5小,我們就選擇走-3這條路,
於是就經過-2->-3->3->1->-5
看起來蠻合理的,
但是某些地圖行不通

譬如說下面這個情況:

1  -3  3
0  -2  0
-3 -3 -3

如果要每次選最小傷害的話,
大概會走1->0->-2->0->-3這條路吧,
這樣需要生命值5才能過關,
然而若走1->-3->3->0->-3這條路只要生命值3就過關了

好似占了局部便宜卻吃了全局虧

實在想不出來,也只好屈服查解答,
學到新的一招

思路- 填表,但從終點往起點填

這個解答就很有趣了,
令給定陣列的名稱為dungeon
想法: 令DP[i][j] 表示以從dungeon[i][j]出發走到右下角,
至少會吃到多少傷害(以負數表示),若不會吃到傷害就以0表示,則
DP[i][j] = min(0, dungeon[i][j] + max(DP[i][j+1], DP[i+1][j]));
因為選擇下一步到終點的傷害較小較有利。

那麼從座標(i, j)出發到右下角需要的生命值也就是-DP[i][j]+1

先上程式碼:

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int R = dungeon.size(), C = dungeon[0].size();
        vector<vector<int>> DP(R, vector<int>(C, 0));
        
        for (int i = R-1; i >= 0; --i) {
            for (int j= C-1; j >= 0; --j) {
                if (i == R - 1 && j == C - 1) {
                    DP[i][j] = min(0, dungeon[i][j]);
                }
                else if (i == R - 1) {
                    DP[i][j] = min(0, dungeon[i][j] + DP[i][j+1]);
                }
                else if (j == C - 1) {
                    DP[i][j] = min(0, dungeon[i][j] + DP[i+1][j]);
                }
                else {
                    DP[i][j] = min(0, dungeon[i][j] + max(DP[i][j+1], DP[i+1][j]));
                }
            }
        }
        return -DP[0][0] + 1;
    }
};

畫個圖演示一下填表的思路:
解說一下為什麼沒吃到傷害要數字要重置為0
比方說我們第三列(row)第二行(column)不是有個30分的生命值嗎?
DP第三列第二行設成-5+30=25行不行呢?

那自然是不行的,因為只要途中騎士生命值歸零就掛了,
後面補血再多也沒用,因此最好情況也只能用0記錄說從這點走到終點是不吃傷害的,
再第二列(row)第二行(column)的值是「-10」,
也就是至少需要11點血量才撐的住,
DP必須老老實實的記下-10
即便下方就有個30分的生命值的大補湯也不會讓需要的生命值變少。

按照我們的算法把DP表格填完之後變這樣:
https://ithelp.ithome.com.tw/upload/images/20200621/20117114o0LMRbodRg.png

那騎士真正闖關時怎麼走呢?
就走下一步到終點受到傷害最小的路線吧
https://ithelp.ithome.com.tw/upload/images/20200621/20117114gjuceJ6Kw5.png

注意這個思路跟「思路二、貪婪的選擇最小傷害路線」不一樣,
思路二是只有看前看一步,
本思路已經把下一步到終點全局至少受到的傷害都算好了。

如果還看不懂的話,
建議讀者可以自己練習一下填DP表格,
並從靠近終點的地方想起,
如果自己站在格子上,
該怎麼走可以用最低生命值過關?

以上這道題就介紹到此,
謝謝觀看


1 則留言

2
I code so I am
iT邦研究生 4 級 ‧ 2020-06-22 09:17:44

有意思。
建議的解法是強化學習 DP 的解法。

心原一馬 iT邦研究生 5 級 ‧ 2020-06-22 13:21:05 檢舉

謝謝。冒昧問一下您指的強化學習 DP 的解法是什麼呢?是Reinforcement learning嗎?

客氣了,是 Reinforcement learning。

我要留言

立即登入留言