Line of wines
2021-02-01 12:13
标签：oss imu ready put -- class row sel tin There are N wines in a row. Each year you sell either the leftmost or the rightmost wine. The i-th wine has initial price p[i] and price k * p[i] in the k-th year. What is the maximum possible total profit? Solution 1. Bottom up dynamic programming state: Loop over i and j. In this case, the loop order matters. In order to compute dp[i][j], we need to have dp[i + 1][j] and dp[i][j - 1] first. This means we need to loop i in decreasing order from N - 1 to 0 and j in increasing order from i + 1 to N - 1. Loop over the interval length first, then loop over all possible left start. Solution II. Top down dynamic programming State: dp[l][r]: the max possible profit before we go to interval [l, r]. dp[l][r] = Math.max(dp[l][r + 1] + p[r + 1] * (currY - 1), dp[l - 1][r] + p[l - 1] * (currY - 1)), currY = N + l - r. Solution III. Bottom up dynamic programming with prefix sum Key idea: if we assume every interval starts with year 1 and already have the max profit for interval[l, r - 1] and [l + 1, r], then to compute interval[l, r], we shift all the years for [l, r - 1] and [l + 1, r] by 1, then add either p[r] or p[l]. This is the prefixsum of interval[l, r]. dp[l][r]: the max possible profit of wines[l, r] starting from year 1. Line of wines 标签：oss imu ready put -- class row sel tin 原文地址：https://www.cnblogs.com/lz87/p/11518228.html
dp[i][j]: the max possible profit of wines[i, j] at year i - 0 + N - 1 - j + 1 = N + i - j
dp[i][j] = max of {p[i] * (N + i - j) + dp[i + 1][j], p[j] * (N + i -j) + dp[i][j - 1]}
Initialization:
dp[i][i] = N * p[i]
Ans:
dp[0][N - 1] public int maxProfitBottomUp(int[] p) {
int N = p.length;
int[][] dp = new int[N][N];
for(int i = 0; i ) {
dp[i][i] = N * p[i];
}
for(int i = N - 1; i >= 0; i--) {
for(int j = i + 1; j ) {
dp[i][j] = Math.max(p[i] * (N + i - j) + dp[i + 1][j], p[j] * (N + i -j) + dp[i][j - 1]);
}
}
return dp[0][N - 1];
}
public int maxProfitBottomUp(int[] p) {
int N = p.length;
int[][] dp = new int[N][N];
for(int i = 0; i ) {
dp[i][i] = N * p[i];
}
for(int len = 2; len ) {
for(int l = 0; l ) {
int r = l + len - 1;
int y = N + l - r;
dp[l][r] = Math.max(p[l] * y + dp[l + 1][r], p[r] * y + dp[l][r - 1]);
}
}
return dp[0][N - 1];
}
Initialization:
dp[0][N - 1] = 0
Answer:
max of {dp[i][i] + p[i] * N} public int maxProfitTopDown(int[] p) {
int N = p.length;
int[][] dp = new int[N][N];
dp[0][N - 1] = 0;
for(int len = N - 1; len >= 1; len--) {
for(int l = 0; l + len ) {
int r = l + len - 1;
int currY = N + l - r;
if(r ) {
dp[l][r] = Math.max(dp[l][r], dp[l][r + 1] + p[r + 1] * (currY - 1));
}
if(l > 0) {
dp[l][r] = Math.max(dp[l][r], dp[l - 1][r] + p[l - 1] * (currY - 1));
}
}
}
int res = 0;
for(int i = 0; i ) {
res = Math.max(res, dp[i][i] + p[i] * N);
}
return res;
}
dp[l][r] = Math.max(dp[l][r - 1], dp[l + 1][r]) + prefixSum[l, r]
init: dp[i][i] = 1 * p[i]
Ans: dp[0][N - 1] public int maxProfitPrefixSum(int[] p) {
int N = p.length;
int[][] dp = new int[N][N];
for(int i = 0; i ) {
dp[i][i] = p[i];
}
int[] prefixSum = new int[N];
prefixSum[0] = p[0];
for(int i = 1; i ) {
prefixSum[i] = prefixSum[i - 1] + p[i];
}
for(int i = N - 1; i >= 0; i--) {
for(int j = i + 1; j ) {
dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]) + prefixSum[j] - (i > 0 ? prefixSum[i - 1] : 0);
}
}
return dp[0][N - 1];
}