歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

有趣的Google面試題 - Harry Potter走矩陣

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];
 }

Copyright © Linux教程網 All Rights Reserved