題目連結：
題目意譯：
魔鬼們擄走了公主並將她囚禁於一個地牢的最右下角。地牢由 m × n 個房間形成的一個二維網格所組成。我們英勇的騎士一開始位於最左上角的房間並且必須一路過關斬將、通過地牢並拯救公主。
騎士有著一個初始血量值以一個正整數代表。如果在任何時刻他的血量值掉至 0 或以下，他將立即死亡。
有些房間將被魔鬼們保衛著（以負整數代表），因此騎士進入這些房間後將損失血量；其他房間要嘛是空的（以 0 代表）、要嘛有著一些可以增加騎士血量的魔法寶珠（以正整數代表）。
為了盡可能地抵達到公主身邊，騎士每一步只會往右或往下移動。
回傳騎士最小的初始生命值，使他可以成功拯救公主。
注意任意房間都可能包含威脅或是增強道具，就算是騎士一開始在的房間或是公主所被囚禁的最右下角之房間也不例外。
限制：
m == dungeon.length
n == dungeon[i].length
1 ≦ m, n ≦ 200
-1000 ≦ dungeon[i][j] ≦ 1000
範例測資：
範例 1：
輸入： dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
輸出： 7
解釋： 騎士的初始血量必須至少為 7 如果他遵循著最佳路徑：右 → 右 → 下 → 下。
範例 2：
輸入： dungeon = [[0]]
輸出： 1
解題思維：
基本精神跟這種題目類似——對答案進行二分搜尋法（Binary Search），在本題即為對血量值二分搜。
那要怎麼檢查一個血量值可不可行呢？使用動態規劃（Dynamic Programming）即可求出：
我們先把整個地牢的座標從左上角為 (0, 0)、右下角為 (m - 1, n - 1) 變成左上角 (1, 1)、右下角 (m, n)。
接著定義一個二維陣列 D[i][j]，代表走到 (i, j) 這個位置時騎士的最大血量值。可以看到初始條件為
D[1][0] = DP[0][1] = 我們要檢查的血量值 B。可以視為騎士在進入最左上角前可以在的兩個位置（左邊以及上面一格）時擁有血量 B，因為有可能進入到左上角血量值就有所變化。
D[i][0] = 0，對於其他的 i 值（因為騎士不會從其他位置出發）；
D[0][j] = 0，對於其他的 j 值（因為騎士不會從其他位置出發）。
而遞迴條件可以看到就是
D[i][j] = max(D[i - 1][j], D[i][j - 1]) + dungeon[i][j]
因此我們就可以從 dungeon 左上角由左至右、從上到下求出所有位置 (i, j) 的 D[i][j] 之值。
注意，當 D[i][j] < 0 時，方便起見我們會將其值設為一個足夠負的值（例如說設成 -1000）。因為 < 0 時代表騎士不管怎麼樣走到 (i, j) 那個位置都會死，而為了避免我們在求其他位置的值時用到 (i, j) 這個位置並避免有「起死回生」這件事情發生，所以我們需要讓 D[i][j] 足夠的小。而每一格最大值可以是 1000，因此設成 -1000 就足夠了。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
