Wednesday, December 2, 2015

Zenefits: The maximum money


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

Solution:
A back-pack DP problem. 

Code (Java):
import java.io.*;
import java.util.*;

public class Solution {
    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];
    }
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] matrix = new int[][]{
            {0, 4, 5},
            {1, 3, 2},
            {0, 1, 1}};
        
        int result = solution.maxCost(matrix, 15);
        System.out.println(result);
    }
}

No comments:

Post a Comment