Buttercola: Zenefits: The maximum money
/*一个正方形的矩阵，左上角的位置保证是0，其他的每个坐标位置上都有一个大于等于0的数。
* 一个人最初携带着的钱数为K，然后要从左上角走到右下角，每次只能向右或者向下走，
* 每到一个位置上就需要花掉该位置上对应的钱数，要求编程看看这个人能不能走到右下角，
* 如果不能，就返回-1，如果能，那就要找到一个解法，使得这个人剩余的钱数尽可能少，
* 也就是最终剩余的钱数要大于等于0，并且尽可能接近于0.*/
Read full article from Buttercola: Zenefits: The maximum money
/*一个正方形的矩阵，左上角的位置保证是0，其他的每个坐标位置上都有一个大于等于0的数。
* 一个人最初携带着的钱数为K，然后要从左上角走到右下角，每次只能向右或者向下走，
* 每到一个位置上就需要花掉该位置上对应的钱数，要求编程看看这个人能不能走到右下角，
* 如果不能，就返回-1，如果能，那就要找到一个解法，使得这个人剩余的钱数尽可能少，
* 也就是最终剩余的钱数要大于等于0，并且尽可能接近于0.*/
public int maxCost(int[][] matrix, int cost) { if (matrix == null || matrix.length == 0 || cost <= 0) { return 0; } int m = matrix.length; int n = matrix[0].length; // dp[i][j][k] means the max cost at i,j with cost limit cost int[][][] dp = new int[m][n][cost + 1]; // Initialize the first row for (int j = 1; j < n; j++) { for (int k = 0; k <= cost; k++) { if (k < matrix[0][j]) { dp[0][j][k] = -1; } else { dp[0][j][k] = dp[0][j][k - matrix[0][j]] + matrix[0][j]; } } } // Initialize the first col for (int i = 1; i < m; i++) { for (int k = 0; k <= cost; k++) { if (k < matrix[i][0]) { dp[i][0][k] = -1; } else { dp[i][0][k] = dp[i][0][k - matrix[i][0]] + matrix[i][0]; } } } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { for (int k = 0; k <= cost; k++) { if (i == 0 && j == 0) { dp[i][j][k] = 0; } else if (k < matrix[i][j]) { dp[i][j][k] = -1; } else { int up = dp[i - 1][j][k - matrix[i][j]]; int left = dp[i][j - 1][k - matrix[i][j]]; if (up == -1 && left == -1) { dp[i][j][k] = -1; } else { dp[i][j][k] = Math.max(up, left) + matrix[i][j]; } } } } } return dp[m - 1][n - 1][cost]; }