http://www.lintcode.com/en/problem/coins-in-a-line-ii/
A Better Solution:
If you notice, we do not need to build complete matrix but only need to build right (upper) triangular matrix. Also notice that C[i, i] (diagonal elements) will always be equal to A[i]. Below is the code which runs in O(n^2) time and takes O(n^2) space.
Also refer to http://tech-queries.blogspot.com/2011/06/get-maximum-sum-from-coins-in-line.html
http://www.danielbit.com/blog/puzzle/leetcode/leetcode-coins-in-a-line
Below is the code which runs in O(n2) time and takes O(n2) space.
http://wlcoding.blogspot.com/2015/03/coins-in-line.html
There are n coins in a line. (Assume n is even). Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.
If you go first, is there a strategy you can follow which prevents you from losing? Try to consider how it matters when the number of coins is odd vs. even.
Solution
Go first can guarantee winning. We can sum up the odd coins and even coins. If odd sum is bigger, we always take the odd coin, and vice versus.
Although this guarantees winning, it does not necessarily yields the max amount of money to win. We can take DP to find out the max.
1. 2-d DP: Time ~ O(N^2), Space ~ O(2N^2)
Let d(i, j) be the maximum amount of money that you can win given the coins [i ... j].
If we take A[i], then the max amount that the opponent will get is d(i + 1, j);
If we take A[j], then the max amount that the opponent will get is d(i, j - 1);
d(i, j) = sum_{k = i}^j A[k] - min{d(i + 1, j), d(i, j - 1)}, i < j
d(i, j) = A[i], i == j
Initialization: NA
Fill up the table: from diagonal to diagonal, move toward upper right (note the for loops for row and column);
Return d(0, N - 1).
2. 2-d DP: Time ~ O(N^2), Space ~ O(N^2)
Improvement: avoid pre-computing and storing sum_{k = i}^j A[k].
Give coins [i ... j], and d(i, j) is defined as the above.
Since the opponent will take the best strategy, he will minimize your winning amount d(i, j).
If we take A[i], d(i, j) = A[i] + min{d(i + 2, j), d(i - 1, j - 1)};
If we take A[j], d(i, j) = A[j] + min{d(i + 1, j - 1), d(i, j - 2)}.
Hence,
d(i, j) = max{A[i] + min{d(i + 2, j), d(i - 1, j - 1)}, A[j] + min{d(i + 1, j - 1), d(i, j - 2)}}, i < j
d(i, j) = A[i], i == j
d(i, j) = max{A[i], A[j]}, i == j - 1
Initialization: NA
Fill up the table: from diagonal to diagonal, move toward upper right (note the for loops for row and column);
Return d(0, N - 1).
II: Optimal Moves
Print out all the moves you and the opponent make, and the total amount of money that you win.
For example, given coins 3, 2, 2, 3, 1, 2.
The result is
Solution
2-d DP: Time ~ O(N^2), Space ~ O(N^2)
Combine the above solution 1 and 2.
1. Use Solution 2 to compute the DP table (from diagonal to diagonal, move towards upper right from middle diagonal, note another way to fill up the table without using row and column);
2. Use Solution 1 to search for a path (from diagonal to diagonal, move towards lower left from upper right conner); For each step, it only needs to compare two entries (if we use Solution 1, we need to compare three entries).
There are n coins with different value in a line. Two players take turns to take one or two coins from left side until there are no more coins left. The player who take the coins with the most value wins.
Could you please decide the first player will win or lose?
Example
Given values array A =
[1,2,2], return true.
Given A =
[1,2,4], return false.- Would you rather go first or second? Does it matter?
- Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.
这道题是之前那道Coins in a Line的延伸，由于每个硬币的面值不同，所以那道题的数学解法就不行了，这里我们需要使用一种方法叫做极小化极大算法Minimax，这是博弈论中比较经典的一种思想，LeetCode上有一道需要用这种思路解的题Guess Number Higher or Lower II。这道题如果没有接触过相类似的题，感觉还是蛮有难度的。我们需要用DP来解，我们定义一个一维数组dp，其中dp[i]表示从i到end可取的最大钱数，大小比values数组多出一位，若n为values的长度，那么dp[n]先初始化为0。我们是从后往前推，我们想如果是values数组的最后一位，及i = n-1时，此时dp[n-1]应该初始化为values[n-1]，因为拿了肯定比不拿大，钱又没有负面额；那么继续往前推，当i=n-2时，dp[n-2]应该初始化为values[n-2]+values[n-1]，应为最多可以拿两个，所以最大值肯定是两个都拿；当i=n-3时，dp[n-3]应该初始化为values[n-3]+values[n-2]，因为此时还剩三个硬币，你若只拿一个，那么就会给对手留两个，当然不行，所以自己要拿两个，只能给对手留一个，那么到目前位置初始化的步骤就完成了，下面就需要找递推式了：
当我们处在i处时，我们有两种选择，拿一个还是拿两个硬币，我们现在分情况讨论：
1. 当我们只拿一个硬币values[i]时，那么对手有两种选择，拿一个硬币values[i+1]，或者拿两个硬币values[i+1] + values[i+2]
a) 当对手只拿一个硬币values[i+1]时，我们只能从i+2到end之间来取硬币，所以我们能拿到的最大硬币数为dp[i+2]
b) 当对手拿两个硬币values[i+1] + values[i+2]时，我们只能从i+3到end之间来取硬币，所以我们能拿到的最大硬币数为dp[i+3]
由于对手的目的是让我们拿较小的硬币，所以我们只能拿dp[i+2]和dp[i+3]中较小的一个，所以对于我们只拿一个硬币的情况，我们能拿到的最大钱数为values[i] + min(dp[i+2], dp[i+3])
a) 当对手只拿一个硬币values[i+1]时，我们只能从i+2到end之间来取硬币，所以我们能拿到的最大硬币数为dp[i+2]
b) 当对手拿两个硬币values[i+1] + values[i+2]时，我们只能从i+3到end之间来取硬币，所以我们能拿到的最大硬币数为dp[i+3]
由于对手的目的是让我们拿较小的硬币，所以我们只能拿dp[i+2]和dp[i+3]中较小的一个，所以对于我们只拿一个硬币的情况，我们能拿到的最大钱数为values[i] + min(dp[i+2], dp[i+3])
2. 当我们拿两个硬币values[i] + values[i + 1]时，那么对手有两种选择，拿一个硬币values[i+2]，或者拿两个硬币values[i+2] + values[i+3]
a) 当对手只拿一个硬币values[i+2]时，我们只能从i+3到end之间来取硬币，所以我们能拿到的最大硬币数为dp[i+3]
b) 当对手拿两个硬币values[i+2] + values[i+3]时，我们只能从i+4到end之间来取硬币，所以我们能拿到的最大硬币数为dp[i+4]
由于对手的目的是让我们拿较小的硬币，所以我们只能拿dp[i+3]和dp[i+4]中较小的一个，所以对于我们只拿一个硬币的情况，我们能拿到的最大钱数为values[i] + values[i + 1] + min(dp[i+3], dp[i+4])
a) 当对手只拿一个硬币values[i+2]时，我们只能从i+3到end之间来取硬币，所以我们能拿到的最大硬币数为dp[i+3]
b) 当对手拿两个硬币values[i+2] + values[i+3]时，我们只能从i+4到end之间来取硬币，所以我们能拿到的最大硬币数为dp[i+4]
由于对手的目的是让我们拿较小的硬币，所以我们只能拿dp[i+3]和dp[i+4]中较小的一个，所以对于我们只拿一个硬币的情况，我们能拿到的最大钱数为values[i] + values[i + 1] + min(dp[i+3], dp[i+4])
综上所述，递推式就有了 dp[i] = max(values[i] + min(dp[i+2], dp[i+3]), values[i] + values[i + 1] + min(dp[i+3], dp[i+4]))
这样当我们算出了dp[0]，知道了第一个玩家能取出的最大钱数，我们只需要算出总钱数，然后就能计算出另一个玩家能取出的钱数，二者比较就知道第一个玩家能否赢了
这样当我们算出了dp[0]，知道了第一个玩家能取出的最大钱数，我们只需要算出总钱数，然后就能计算出另一个玩家能取出的钱数，二者比较就知道第一个玩家能否赢了
定义dp[i]表示从i到end能取到的最大值
当我们在i处，有两种选择：
1.若取values[i]，对方可以取values[i+1] 或者values[i+1] + values[i+2]
当对方取values[i+1] 后 ，我们只能从 i+2 到end内取，我们所取得最大值是dp[i+2], 注意：对方所选取的结果一定是使得我们以后选取的值最小
当对方取values[i+1] + values[i+2]后，我们只能从i+3到end内取，我们所取得最大值是dp[i+3]。
此时：dp[i] = values[i] + min(dp[i+2],dp[i+3]) , 注意：对方所选取的结果一定是使得我们以后选取的值最小
2.若取values[i] + values[i+1],对方可取values[i+2] 或者values[i+2] + values[i+3]
当对方取values[i+2]后，我们只能从i+3到end内取，我们取得最大值是dp[i+3]
当对方取values[i+2]+values[i+3]后，我们只能从i+4到end内去，我们取得最大值是dp[i+4]
此时：dp[i] = values[i] + values[i+1]+min(dp[i+3],dp[i+4])
这里的取最小值和上面一样的意思，对方选取过之后的值一定是使得我们选取的值最小，对方不傻并且还很聪明
最后我们可以取上面两个dp[i]的最大值，就是答案，这里意思是：对方留得差的方案中，我们选取的最大值。
public boolean firstWillWin(int[] values) { // write your code here // dp 表示从i到end 的最大值 // int values[] ={1,2,4,3,4,8,5,6,12}; int len = values.length; // 长度小于2的时候第一个人一定获胜 if(len <= 2) return true; int dp[] = new int[len+1]; dp[len] = 0; dp[len-1] = values[len-1]; dp[len-2] = values[len-1] + values[len - 2]; dp[len - 3] = values[len-3] + values[len - 2]; for(int i = len -4;i>=0;i--){ dp[i] = values[i] + Math.min(dp[i+2],dp[i+3]); dp[i] = Math.max(dp[i],values[i]+values[i+1]+ Math.min(dp[i+3],dp[i+4])); } int sum = 0; for(int a:values) sum +=a; return dp[0] > sum - dp[0]; }
Let us look one extra step ahead this time by considering the two coins the opponent will possibly take, Ai+1 and Aj. If the opponent takes Ai+1, the remaining coins are { Ai+2 … Aj }, which our maximum is denoted by P(i+2, j). On the other hand, if the opponent takes Aj, our maximum is P(i+1, j-1). Since the opponent is as smart as you, he would have chosen the choice that yields the minimum amount to you.
Therefore, the maximum amount you can get when you choose Ai is:
P1 = Ai + min { P(i+2, j), P(i+1, j-1) }
Similarly, the maximum amount you can get when you choose Aj is:
P2 = Aj + min { P(i+1, j-1), P(i, j-2) }
Therefore,
P(i, j) = max { P1, P2 }
= max { Ai + min { P(i+2, j), P(i+1, j-1) },
Aj + min { P(i+1, j-1), P(i, j-2) } }
We can store values of Sum{Ai … Aj} in a table and avoid re-computations by computing in a certain order.If you notice, we do not need to build complete matrix but only need to build right (upper) triangular matrix. Also notice that C[i, i] (diagonal elements) will always be equal to A[i]. Below is the code which runs in O(n^2) time and takes O(n^2) space.
const int MAX_N = 100;
int maxMoney(int A[], int N) {
int P[MAX_N][MAX_N] = {0};
int a, b, c;
for (int i = 0; i < N; i++) {
for (int m = 0, n = i; n < N; m++, n++) {
assert(m < N); assert(n < N);
a = ((m+2 <= N-1) ? P[m+2][n] : 0);
b = ((m+1 <= N-1 && n-1 >= 0) ? P[m+1][n-1] : 0);
c = ((n-2 >= 0) ? P[m][n-2] : 0);
P[m][n] = max(A[m] + min(a,b),
A[n] + min(b,c));
}
}
printMoves(P, A, N);
return P[0][N-1];
}
void printMoves(int P[][MAX_N], int A[], int N) {
int sum1 = 0, sum2 = 0;
int m = 0, n = N-1;
bool myTurn = true;
while (m <= n) {
int P1 = P[m+1][n]; // If take A[m], opponent can get...
int P2 = P[m][n-1]; // If take A[n]
cout << (myTurn ? "I" : "You") << " take coin no. ";
if (P1 <= P2) {
cout << m+1 << " (" << A[m] << ")";
m++;
} else {
cout << n+1 << " (" << A[n] << ")";
n--;
}
cout << (myTurn ? ", " : ".\n");
myTurn = !myTurn;
}
cout << "\nThe total amount of money (maximum) I get is " << P[0][N-1] << ".\n";
}
Assume that your opponent is so dumb that you are able to manipulate him into choosing the coins you want him to choose. Now, what is the maximum possible amount of money you can win?Also refer to http://tech-queries.blogspot.com/2011/06/get-maximum-sum-from-coins-in-line.html
http://www.danielbit.com/blog/puzzle/leetcode/leetcode-coins-in-a-line
Below is the code which runs in O(n2) time and takes O(n2) space.
dp[i][j]代表从第i个硬币到第j个硬币这个子问题的结果，也就是可以拿到的最大钱数。sum[i][j]代表从第i个硬币到第j个硬币总钱数之和
那么对于每一个子问题，你有两种选择
1）如果你取第一个的话，剩下的子问题就变成了(i+1,j)了，由于轮到对方取了，因此对方可以得到dp[i+1][j]的钱数，而你则得到sum[i+1,j]-dp[i+1][j]的钱数，也就是剩余的钱数。
2）如果你取最后一个的话，同理。
递推公式为：
dp[i][j] = max(sum[i][j]-dp[i+1][j], sum[i][j]-dp[i][j-1]) = sum[i][j]-min(dp[i+1][j],dp[i][j-1])
[注意事项]
1）这道问题看起来想是一维的DP，但需要用二维DP来求解
1）这道问题看起来想是一维的DP，但需要用二维DP来求解
int coins(int[] A) { int n=A.length; int[][] sum=new int[n][n]; int[][] dp=new int[n][n]; for(int i=n-1;i>=0;i--) for(int j=i;j<n;j++) sum[i][j]=A[j]+(i==j?0:sum[i][j-1]); for(int i=n-1;i>=0;i--) for(int j=i;j<n;j++) { if(i==j) dp[i][j]=A[i]; else dp[i][j]=sum[i][j]-Math.min(dp[i+1][j], dp[i][j-1]); } return dp[0][n-1]; }http://techinpad.blogspot.com/2015/05/lintcode-coins-in-line-iii.html
- bool firstWillWin(vector<int> &values) {
- int len = values.size();
- if(len<=2) return true;
- vector<vector<int>> f(len, vector<int>(len,0));
- for(int i=0;i<len;i++) f[i][i] = values[i];
- for(int i=len-2;i>=0;i--)
- {
- for(int j=i+1;j<len;j++)
- {
- f[i][j] = max(values[i] - f[i+1][j], values[j] - f[i][j-1]);
- }
- }
- return f[0][len-1] > 0;
- }
http://wlcoding.blogspot.com/2015/03/coins-in-line.html
There are n coins in a line. (Assume n is even). Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.
- Would you rather go first or second? Does it matter?
- Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.
If you go first, is there a strategy you can follow which prevents you from losing? Try to consider how it matters when the number of coins is odd vs. even.
Solution
Go first can guarantee winning. We can sum up the odd coins and even coins. If odd sum is bigger, we always take the odd coin, and vice versus.
Although this guarantees winning, it does not necessarily yields the max amount of money to win. We can take DP to find out the max.
Assume both you and the opponent are taking the coins in an optimal way.
Let d(i, j) be the maximum amount of money that you can win given the coins [i ... j].
If we take A[i], then the max amount that the opponent will get is d(i + 1, j);
If we take A[j], then the max amount that the opponent will get is d(i, j - 1);
d(i, j) = sum_{k = i}^j A[k] - min{d(i + 1, j), d(i, j - 1)}, i < j
d(i, j) = A[i], i == j
Initialization: NA
Fill up the table: from diagonal to diagonal, move toward upper right (note the for loops for row and column);
Return d(0, N - 1).
public int maxMoney(int[] A) { int N = A.length; int[][] sumA = new int[N][N]; for (int i = 0; i < N; i++) for (int j = i; j < N; j++) sumA[i][j] = ((i == j) ? 0 : sumA[i][j - 1]) + A[j]; int[][] d = new int[N][N]; for (int i = 0; i < N; i++) for (int j = 0; j < N - i; j++) { int r = j, c = i + j; d[r][c] = (r == c) ? A[r] : (sumA[r][c] - Math.min(d[r + 1][c], d[r][c - 1])); } return d[0][N - 1]; }
2. 2-d DP: Time ~ O(N^2), Space ~ O(N^2)
Improvement: avoid pre-computing and storing sum_{k = i}^j A[k].
Give coins [i ... j], and d(i, j) is defined as the above.
Since the opponent will take the best strategy, he will minimize your winning amount d(i, j).
If we take A[i], d(i, j) = A[i] + min{d(i + 2, j), d(i - 1, j - 1)};
If we take A[j], d(i, j) = A[j] + min{d(i + 1, j - 1), d(i, j - 2)}.
Hence,
d(i, j) = max{A[i] + min{d(i + 2, j), d(i - 1, j - 1)}, A[j] + min{d(i + 1, j - 1), d(i, j - 2)}}, i < j
d(i, j) = A[i], i == j
d(i, j) = max{A[i], A[j]}, i == j - 1
Initialization: NA
Fill up the table: from diagonal to diagonal, move toward upper right (note the for loops for row and column);
Return d(0, N - 1).
public int maxMoney(int[] A) { int N = A.length; int[][] d = new int[N][N]; for (int i = 0; i < N; i++) for (int j = 0; j < N - i; j++) { int r = j, c = i + j; if (r == c) d[r][c] = A[r]; else if (r == c - 1) d[r][c] = Math.max(A[r], A[c]); else d[r][c] = Math.max(A[r] + Math.min(d[r + 2][c], d[r + 1][c - 1]), A[c] + Math.min(d[r + 1][c - 1], d[r][c - 2])); } return d[0][N - 1]; }
II: Optimal Moves
Print out all the moves you and the opponent make, and the total amount of money that you win.
For example, given coins 3, 2, 2, 3, 1, 2.
The result is
"I take 3
You take 2
I take 2
You take 1
I take 3
You take 2
The total amount of money that I get is 8"
Solution
2-d DP: Time ~ O(N^2), Space ~ O(N^2)
Combine the above solution 1 and 2.
1. Use Solution 2 to compute the DP table (from diagonal to diagonal, move towards upper right from middle diagonal, note another way to fill up the table without using row and column);
2. Use Solution 1 to search for a path (from diagonal to diagonal, move towards lower left from upper right conner); For each step, it only needs to compare two entries (if we use Solution 1, we need to compare three entries).
public String printMoves(int[] A) { int N = A.length; int[][] d = new int[N][N]; // compute DP table d[][] for (int i = N - 1; i >= 0; i--) for (int j = i; j < N; j++) { if (i == j) d[i][j] = A[i]; else if (i == j - 1) d[i][j] = Math.max(A[i], A[j]); else d[i][j] = Math.max(A[i] + Math.min(d[i + 2][j], d[i + 1][j - 1]), A[j] + Math.min(d[i + 1][j - 1], d[i][j - 2])); } // generate the path StringBuilder str = new StringBuilder(); boolean myTurn = true; int r = 0, c = N - 1; while (r <= c) { if (myTurn) str.append("I take "); else str.append("You take "); myTurn = !myTurn; if (d[r + 1][c] < d[r][c - 1]) str.append(A[r++]); else str.append(A[c--]); str.append("\n"); } str.append("The total amount of money that I get is " + d[0][N - 1]); return str.toString(); }Read full article from Coins in a Line | LeetCode
