MITBBS上看了一道有趣的G家面試題，題目如下：
有一個2維矩陣，假設你是Harry Potter，在矩陣的左上角，你現在要走到右下角。矩陣中每個點都有一個權值，有正數也有負數，遇到正數表示你的生命力能增加那麼多，遇到負數表示生命力減少那麼多，在任何時刻如果你的生命力小於0，那麼你就掛了。在一開始你有一定的初始生命力，現在問這個初始的生命力最少是多少，才能保證你能夠找到一條路。走到右下角。每一步只能向右或者向下。
其實這個題目看起來很像LeetCode裡的Minimum Path Sum,也是從左上角走到右下角，只不過這裡不是求總權值最小的路徑而已。那麼這題是不是用同樣的方法就可以解決了呢？現在分析下題目的相似處和不同處。
相似處：都是求最優解問題，而且都具有遞歸性質。一般這種題目要麼用貪心，要麼用DP。稍微分析下，這裡用貪心肯定不行的，如果一開始碰到兩個權值都為正的方向，直接貪心地選擇走權值更大的那個，那麼之後如果遇到一個無法預見的很大的負權值的點，顯然就會吃虧。由此觀之，局部最優無法保證全局最優，故解題思路應該為DP。
不同處：
1）這裡一個重要的條件是生命值在任何時刻都必須不能為負數，所以如果簡單的考慮講到達終點時的生命值最大化，不一定能保證此題的最優解。
考慮如下矩陣：
0 0 0 0
0 0 -6 0
0 -5 20 0
0 0 0 1
容易看出，這裡走通過-5和20的路徑可以保證最後的生命值最大化，然而由於之前必須經過一個負權值點，所以這裡最小的初始生命值為5。然而其實此題明顯最優解是直接走兩個邊路中的一個，初始生命值為0即可。
2）使用DP時，除了需要歸納出遞歸表達式意外，還需要找到自底向上的base case。其實這個base case是可以引導推理的方向的。在Minimum Path Sum題目裡，顯然base case是在左上角時，因為最小的和就是當前左上角這個點的權值了。這樣一來，從左上角往右下角推理會很順暢。這一題中，左上角的值其實是所求，而base case其實應該在右下角，必須在終點的時候不為負數。（在起點的時候生命值僅僅不為負是無法保證能夠一直走完全程的。）所以，這題應該從右下角往左上角推理。
如果設M和N分別為矩陣的兩邊長，dp[i][j]表示在沒有加上matrix[i][j]的權值之前所需的最小的生命值，我們這題其實就是求的dp[0][0]。
Base Case: 對於最右下角，由於需要dp[M - 1][N - 1] + matrix[i][j] >= 0，可以得到dp[M - 1][N - 1] >= -matrix[i][j]。如果這裡的matrix[i][j]為正數，那麼dp[M - 1][N - 1]最小值就為負數，是題目不允許的，所以：
dp[M - 1][N - 1] = MAX{-1 * matrix[M - 1][N - 1], 0}
Recursion: 對於任意一個dp[i][j],
1）如果向下延伸至dp[i + 1][j]，可得dp[i][j] + matrix[i][j] >= dp[i + 1][j]，且dp[i][j] >= 0。所以 dp[i][j] = MAX{dp[i + 1][j] - matrix[i][j], 0}
2）如果向右延伸至dp[i][j + 1]，可得dp[i][j] + matrix[i][j] >= dp[i][j + 1]，且dp[i][j] >= 0。所以 dp[i][j] = MAX{dp[i][j + 1] - matrix[i][j], 0}
綜上，dp[i][j] = MIN{ MAX{dp[i + 1][j] - matrix[i][j], 0}, MAX{dp[i][j + 1] - matrix[i][j], 0} }。
注意，另外兩條邊上的dp值只需要沿一個方向遞歸，所以需要特殊處理。代碼如下：
public int minStrength(int[][] matrix) {
int M = matrix.length, N = matrix[0].length;
int[][] dp = new int[M][N];
dp[M - 1][N - 1] = Math.max(-1 * matrix[M - 1][N - 1], 0);
for (int i = M - 2; i >= 0; i--) {
dp[i][N - 1] = Math.max(dp[i + 1][N - 1] - matrix[i][N - 1], 0);
}
for (int i = N - 2; i >= 0; i--) {
dp[M - 1][i] = Math.max(dp[M - 1][i + 1] - matrix[M - 1][i], 0);
}
for (int i = M - 2; i >= 0; i--) {
for (int j = N - 2; j >= 0; j--) {
dp[i][j] = Math.min(Math.max(dp[i + 1][j] - matrix[i][j], 0),
Math.max(dp[i][j + 1] - matrix[i][j], 0));
}
}
return dp[0][0];
}
