## Thursday, December 3, 2015

### Buttercola: Zenefits: The maximum money

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