Cost Matrix - Zenefits

http://www.1point3acres.com/bbs/thread-145290-1-1.html

/*一个正方形的矩阵，左上角的位置保证是0，其他的每个坐标位置上都有一个大于等于0的数。 * 一个人最初携带着的钱数为K，然后要从左上角走到右下角，每次只能向右或者向下走， * 每到一个位置上就需要花掉该位置上对应的钱数，要求编程看看这个人能不能走到右下角， * 如果不能，就返回-1，如果能，那就要找到一个解法，使得这个人剩余的钱数尽可能少， * 也就是最终剩余的钱数要大于等于0，并且尽可能接近于0.*/

1.         public int findMaxSpent(int[][] mat, int k){
2.                 // dp[i][j][n] is the max mount spent at i,j but less than n. 1point 3acres 璁哄潧
3.                 // dp[i][j][n] = max(dp[i - 1][j][n - mat[i][j]], dp[i][j - 1][n - mat[i][j]])
4.                 int m = mat.length;. more info on 1point3acres.com
5.                 if (m == 0) return -1;
6.                 int n = mat[0].length; 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�. 
7.                 int[][] dp1 = new int[n + 1][k + 1];
8.                 int[][] dp2 = new int[n + 1][k + 1];
9.                 // when i == -1; edge case
10.                 for (int j = 0; j < n; j++){
11.                         for (int h = 0; h <= k; h++){
12.                                 dp1[j + 1][h] = -1;-google 1point3acres
13.                         }
14.                 }
15.                 // when j = -1 edge case
16.                 for (int h = 0; h <= k; h++){
17.                         dp2[0][h] = -1;
18.                 }
19.                 .鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
20.                 for (int i = 0; i < m; i++){
21.                         for (int j = 0; j < n; j++){
22.                                 for (int h = 0; h <= k; h++){
23.                                         if (i == 0 && j == 0) dp2[j + 1][h] = 0;
24.                                         else if (h < mat[i][j]) dp2[j + 1][h] = -1;. From 1point 3acres bbs
25.                                         else {
26.                                                 int pre1 = dp2[j][h - mat[i][j]];. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
27.                                                 int pre2 = dp1[j + 1][h - mat[i][j]];
28.                                                 if (pre1 == -1 && pre2 == -1) dp2[j + 1][h] = -1;
29.                                                 else dp2[j + 1][h] = Math.max(pre1, pre2) + mat[i][j];
30.                                         }
31.                                 }
32.                         }. Waral 鍗氬鏈夋洿澶氭枃绔�,
33.                         dp1 = Arrays.copyOf(dp2, n + 1);
34.                 }. 鍥磋鎴戜滑@1point 3 acres
35.                 return dp1[n][k];
36.         }
37.         . 鍥磋鎴戜滑@1point 3 acres
38.         public static void main(String[] args){
39.                 Solution sln = new Solution();
40.                 int[][] mat = {{0,4,5}, {1,3,2}, {0,1,1}};. from: 1point3acres.com/bbs 
41.                 System.out.println(sln.findMaxSpent(mat, 12));
42.         }
43. }