1937. Maximum Number of Points with Cost
Latest:
https://www.youtube.com/watch?v=ik1y7fz8AOc
class Solution {
public long maxPoints(int[][] points) {
int m = points.length;
int n = points[0].length;
long[] prevRow = new long[n];
long[] curRow = new long[n];
for (int j = 0; j < n; j++) { // for big number add...use long
prevRow[j] = points[0][j];
}
long result = 0;
for (int i = 1; i < m; i++) {
long[] leftMax = new long[n];
long[] rightMax = new long[n];
leftMax[0] = prevRow[0];
for (int j = 1; j < n; j++) {
leftMax[j] = Math.max(leftMax[j-1] - 1, prevRow[j]);
}
rightMax[n-1] = prevRow[n-1];
for (int j = n-2; j >= 0; j--) {
rightMax[j] = Math.max(rightMax[j+1] - 1, prevRow[j]);
}
for (int j = 0; j < n; j++) {
curRow[j] = points[i][j];
curRow[j] += Math.max(leftMax[j], rightMax[j]);
}
prevRow = curRow;
}
for (int j = 0; j < n; j++) {
result = Math.max(result, prevRow[j]); // for only one row case, if it's one row, then ans is in prevRow
}
return result;
}
}
/**
cal left max array
right max
if m = 3, left start from 1 , right start from m-2
left max = left[1] = max(left[1-1] - 1, prev_row[1])
right max = right[1] = max(right[3-2] - 1, prev_row[1])
so we can have left max and right max
curr_row[1] = curr_row[1] + max(left_max[1], right_max[1])
continuously cal to last row, then ans is the max(last_row)
1 2 3
left max for 5 ->. 5 + max(1a - 1, 2) = 7
1a 5 1c
right max for 5. -> 5 + max(1c -1, 2) = 7
1. 2 3
left. 1. 2 3
right 1 2 3
1 5.1 -> 1 + max(1, 1), 5 + max(2, 2), 1 + max(3, 3) =
2 7 4
so 1 5 1 to
2 7 4
left 2 7 6
right 6 7 4
3 1 1. 3 + max(left[0], right[0]) = 3 + max(2, 6) = 9
9 8 7. ->. max(last row) = 9
so this way is
T: O(mn), m is row, n is col, for each row, cal left_max (n), and right_max(n) -> m*(2n)
S: O(n), left_max, right_max array
*/
like 931, 但分支太多, 所以 dfs + memo 會不過 (931 只有 3個分支, 這題有 n 個分支（n is num of col)
DFS + memo (Time Limit Exceeded
T: O(col^row)
S: O(row*col)
class Solution {
public long maxPoints(int[][] points) {
int m = points.length;
int n = points[0].length;
Long[][] memo = new Long[m][n];
long max = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) { // each cell in row 0
max = Math.max(max, dfs(points, 0, i, memo));
}
return max;
}
private long dfs(int[][] points, int row, int col, Long[][] memo) {
int m = points.length;
int n = points[0].length;
if(row == m - 1) {
return points[row][col];
}
if (memo[row][col] != null) {
return memo[row][col];
}
long max = Long.MIN_VALUE;
for (int i = 0; i < n; i++) {
// notice, in dfs, run (row+1, all cols)
long sum = points[row][col] + dfs(points, row+1, i, memo) - Math.abs(col - i);
max = Math.max(max, sum);
}
memo[row][col] = max;
return max;
}
}
/*
row 0, col 0~3
p(0,0)
+
(r+1, col i 0~3) - abs|i - col|
[
[1,2,3],
[1,5,1], 7
[3,1,1]]
[
[1,5],
[2,3],
[4,2]]
*/DP
class Solution {
public long maxPoints(int[][] points) {
int m = points.length;
int n = points[0].length;
long[][] dp = new long[m][n];
for (int j = 0; j < n; j++) {
dp[0][j] = points[0][j]; // first row value
}
for (int i = 1; i < m; i++) {
long rollingMax = Long.MIN_VALUE; // 每次 row 都會拿到一個最大值, 所以要宣告在這
for (int j = 0; j < n; j++) {
// System.out.println("i:"+i);
// System.out.println("dp[i-1][j]:"+dp[i-1][j]+",j:"+ j);
// System.out.println("dp[i-1][j] + j:"+ (dp[i-1][j] + j)+"\n");
rollingMax = Math.max(rollingMax, dp[i-1][j] + j);
// System.out.println("rollingMax:" + rollingMax);
dp[i][j] = Math.max(dp[i][j], (points[i][j] - j) + rollingMax);
}
rollingMax = Long.MIN_VALUE;
for (int j = n-1; j >= 0; j--) { // why reverse?
// System.out.println("i:"+i);
// System.out.println("dp[i-1][j]:"+dp[i-1][j]+",j:"+ j);
// System.out.println("dp[i-1][j] - j:"+ (dp[i-1][j] - j)+"\n");
rollingMax = Math.max(rollingMax, dp[i-1][j] - j);
// System.out.println("rollingMax:" + rollingMax);
dp[i][j] = Math.max(dp[i][j], (points[i][j] + j) + rollingMax);
}
}
/*[
[1,5],
[2,3],
[4,2]]
*/
long res = Long.MIN_VALUE;
for (int j = 0; j < n; j++) {
res = Math.max(res, dp[m-1][j]);
}
return res;
}
}
/*
sol 1.
for (int i = 0 ~m)
for (int j = 0~n)
for(int k = 0 ~n)
dp[i][j] = Max(points[i][j] + dp[i-1][k] + abs(j-k))
T: O(m*n*n), => TLE, m, n is 10^5, too big
sol 2.
T: O(m*n)
dp[i][j] = from row 0~m-1, points[i][j] which is the maximum points you can obtain
dp[i][j] = Max(points[i][j] + dp[i-1][k] + abs(j-k)) =>
when j-k >= 0
dp[i][j] = (points[i][j] + j) + max(dp[i-1][k] -k), k= 0, 1, ...~j (從0 開始滾)
dp[i][0] = (points[i][0] + 0) + max(dp[i-1][0] -0)
dp[i][1] = (points[i][1] + 1) + max(dp[i-1][0] -0, dp[i-1][1] -1)
dp[i][2] = (points[i][2] + 2) + max(dp[i-1][0] -0, dp[i-1][1] -1, dp[i-1][2] -2 )...
=>
for (int i = 1 ~m)
for (int j = 0~n)
int rollingMax = Math.max(rollingMax, dp[i-1][j] +j);
dp[i][j] = Math.max(dp[i][j], (points[i][j] - j) + rollingMax);
when j-k <= 0, 就反過來
dp[i][j] = (points[i][j] - j) + max(dp[i-1][k] + k), k= j, j+1, ...~n-1 (從 n-1 開始滾)
為什麼. for k>=j 時
for (int j=n-1; j>=0; j--)
{
rollingMax = max(rollingMax, dp[i-1][j]-j);
dp[i][j] = max(dp[i][j], rollingMax +points[i][j] + j);
}
一定要從 n-1 後面 rolling 過來呢
因為這裡是 -k, 所以從後面大的開始滾, max 的值會從小到大滾出來
for (int i = 1 ~m)
for (int j = 0~n)=> 這不行, 要到序
int rollingMax = Math.max(rollingMax, dp[i-1][j] - j);
dp[i][j] = Math.max(dp[i][j], (points[i][j] + j) + rollingMax);
*/another explain
/*
for i
for j
for (k = 0~n) {
dp[i][j] = max(dp[i-1][k] - abs(j - k)) + A[i][j]
}
how to reduce for (k = 0~n), this part?
abs(j-k) => can be two cases
1. j - k >= 0 => - abs(j - k) => -(j - k) = k - j, k = 0~j
dp[i][j] = max(dp[i-1][k] + abs(j - k)) + A[i][j]
rolling part
= max(dp[i-1][k] + k) - j + A[i][j]
2. j - k <= 0 => - j + k
rolling part
= max(dp[i-1][k] - k) + j + A[i][j]
rolling max:
max(dp[i-1][k] + k) , k = 0 ~ j
for small to max : start from 0 to n-1 rolling
max(dp[i-1][k] - k) , k = j~n-1
for small to max : start from n-1 to 0 rolling
T: O(mn)
S: O(mn)
*//*
dp[i][j] = Max(dp[i-1][k] - abs(j-k) + point[i][j])
=>
for (int i)
for (int j)
for (int k)
how to optimized?
j - k >= 0, k = 0~j
dp[i][j] = max(point[i][j] + dp[i-1][k] - j + k)
=>
dp[i][j] = max(dp[i-1][k] + k) + point[i][j] - j
k = 0~j
dp[i][0] = max(dp[i-1][0] + 0) + point[i][0] - 0
dp[i][1] = max(dp[i-1][0] + 0, dp[i-1][1] + 1) + point[i][1] - 1
dp[i][2] = max(dp[i-1][0] + 0, dp[i-1][1] + 1, dp[i-1][2] + 2) + point[i][2] - 2
for (int i)
for (int j)
long rollingMax = max(rollingMax, dp[i-1][j] + j)
dp[i][j] = max(dp[i][j], rollingMax + point[i][j] - j)
----------------------
j - k <= 0, k = j ~ n
dp[i][j] = dp[i-1][k] + j - k
=>
dp[i][j] = dp[i-1][k] - k + j
for (int i)
for (int j)
long rollingMax = max(rollingMax, dp[i-1][j] - j)
dp[i][j] = max(dp[i][j], rollingMax + point[i][j] + j)
at last find max in dp[m-1][0~n]
*/Last updated