Interval Dynamic Programming | Coin Game
Interval DP is another sub-type of the dynamic programming technique that deals with ranges or intervals. In general, the final answer to interval DP problems will be the answer to the entire range [1, n]
, where subproblems are computed by finding the answer to all possible ranges, [l, r]
where l <= r
. Alternate names for interval DP are left-right DP or L-R DP.
Interval DP is one of the more challenging types of dynamic programming problems. They might be too difficult for the real interviews. We are including them here for completeness. Don't sweat if you can't get it the firs time.
Coin Game
There are n
coins in a straight line. The i
th coin has a value of coins[i]
.
You play this game with a friend alternating turns, starting with you, remove
one coin from one end of the line and add that coin's value to your score.
If your friend plays perfectly in such a way that maximizes their score, what is your maximum possible score?
Input
coins
: A list of the coins.
Output
Your maximum possible score, provided that you go first and your friend plays perfectly.
Examples
Example 1:
Input:
1coins = [4, 4, 9, 4]
Output: 13
Explanation:
The coins start like this:
4, 4, 9, 4
You always go first, so you take the 4 from the left side:
4, 9, 4
Your friend takes any of the 4s (it doesn't matter)
9, 4
Now you take the 9, and your friend takes the remaining 4.
Your score in this case, is 4 + 9 = 13.
Constraints
1 <= len(coins) <= 1000
1 <= coins[i] <= 5 * 10^5
Try it yourself
Solution
Brute Force
A brute force solution would enumerate through all possibilities. For each of the n
turns, we either choose the left-most coin or the right-most coin and check which option maximizes our score.
The 2 cases mentioned above are described as follows:
- Case 1: We take coin
l
- Coins in the range
[l + 1, r]
are left - Since our opponent plays optimally, they will gain points equal to
maxScore(l + 1, r)
- Since we get all other coins, our score will be
sum(l, r) - maxScore(l + 1, r)
- Coins in the range
- Case 2: We take coin
r
- Coins in range
[l, r - 1]
are left - Since our opponent plays optimally, they will gain points equal to
maxScore(l, r - 1)
- Since we get all other coins, our score will be
sum(l, r) - maxScore(l, r - 1)
- Coins in range
Next, we choose the case that gives us the greatest score, or minimizes the opponent's score. Therefore, the solution is either:
maxScore(l, r) = max(sum(l, r) - maxScore(l + 1, r), sum(l, r) - maxscore(l, r - 1))
ormaxScore(l, r) = sum(l, r) - min(maxScore(l + 1, r), maxScore(l, r - 1))
Note that a common pitfall is to try to keep tracking of which player the current recursive call is for using an extra state variable. This is unnecessary because it doesn't really matter which user the recursive call is for because the current player always tries to minimize the other player's score (each user "plays perfectly in such a way that maximizes their score"). Each recursive call returns the best possible score the current player can get. The outermost call will return the best score for the first player.
Since there are n
turns, 2 possibilities each turn, and takes O(n)
to calculate the sum from l
to r
,
the final runtime is O(n * 2^n)
.
Here's a visual representation of the idea:
The following is an implementation of the idea above:
1int max_score(vector<int> coins, int l, int r) {
2 if (l == r) {
3 return coins[r];
4 }
5
6 int sum = 0;
7 for (int i = l; i <= r; i++) {
8 sum += coins[i];
9 }
10
11 int left_pick = max_score(coins, l + 1, r);
12 int right_pick = max_score(coins, l, r - 1);
13 return sum - min(left_pick, right_pick);
14}
15
16int coin_game(vector<int> coins) {
17 int n = coins.size();
18 return max_score(coins, 0, n - 1);
19}
20
1public static int maxScore(List<Integer> coins, int l, int r) {
2 if (l == r) {
3 return coins.get(r);
4 }
5
6 int sum = 0;
7 for (int i = l; i <= r; i++) {
8 sum += coins.get(i);
9 }
10
11 int leftPick = maxScore(coins, l + 1, r);
12 int rightPick = maxScore(coins, l, r - 1);
13 return sum - Math.min(leftPick, rightPick);
14}
15
16public static int coinGame(List<Integer> coins) {
17 int n = coins.size();
18 return maxScore(coins, 0, n - 1);
19}
20
1function maxScore(coins, l, r) {
2 if (l === r) {
3 return coins[r];
4 }
5
6 var sum = 0;
7 for (let i = l; i <= r; i++) {
8 sum += coins[i];
9 }
10
11 var leftPick = maxScore(coins, l + 1, r);
12 var rightPick = maxScore(coins, l, r - 1);
13 return sum - Math.min(leftPick, rightPick);
14}
15
16function coinGame(coins) {
17 let n = coins.length;
18 return maxScore(coins, 0, n - 1);
19}
20
1def max_score(coins, l, r):
2 if l == r:
3 return coins[r]
4
5 sum = 0
6 for i in range(l, r + 1):
7 sum += coins[i]
8
9 left_pick = max_score(coins, l + 1, r)
10 right_pick = max_score(coins, l, r - 1)
11 return sum - min(left_pick, right_pick)
12
13def coin_game(coins):
14 n = len(coins)
15 return max_score(coins, 0, n - 1)
16
Slight Optimization
So far, for each recursive call we are spending O(n)
time to calculate the sum between the range [l, r]
. However, instead of using O(n)
every time we need the sum we can use a prefix sum array to get the range sum in O(1)
time and a single O(n)
pre-computation.
1 | 1 |
| |
2 | + |
| |
2 | 3 |
| |
3 | - |
| |
4 | + |
| |
4 | 5 |
| |
5 | 6 | ||
6 | - |
| |
7 | - |
| |
8 | - |
| |
9 | - |
| |
10 | - |
| |
11 | 7 |
| |
12 | 8 |
| |
13 | 9 |
| |
14 | 10 |
| |
15 | 11 |
| |
16 | 12 |
| |
17 | - |
| |
13 | + |
| |
14 | + |
| |
15 | + |
| |
16 | + |
| |
17 | + | ||
18 | + |
| |
18 | 19 |
|
1 | 1 |
| |
2 | + |
| |
2 | 3 |
| |
3 | - |
| |
4 | + |
| |
4 | 5 |
| |
5 | - |
| |
6 | - |
| |
7 | - |
| |
8 | - |
| |
9 | - |
| |
10 | 6 |
| |
11 | 7 |
| |
12 | 8 |
| |
13 | 9 |
| |
14 | 10 |
| |
15 | 11 |
| |
16 | - |
| |
12 | + |
| |
13 | + |
| |
14 | + |
| |
15 | + |
| |
16 | + |
| |
17 | + |
| |
17 | 18 |
|
1 | 1 |
| |||
2 | + |
| |||
2 | 3 |
| |||
3 | - |
| |||
4 | + |
| |||
4 | 5 |
| |||
5 | 6 | ||||
6 | - |
| |||
7 | - |
| |||
8 | - |
| |||
9 | - |
| |||
10 | - |
| |||
11 | 7 |
| |||
12 | 8 |
| |||
13 | 9 |
| |||
14 | 10 |
| |||
Expand 1 lines ... | |||||
16 | 12 |
| |||
17 | 13 |
| |||
18 | - |
| |||
14 | + |
| |||
15 | + |
| |||
16 | + |
| |||
17 | + |
| |||
18 | + |
| |||
19 | 19 |
|
1 | 1 |
| |
2 | + |
| |
2 | 3 |
| |
3 | - |
| |
4 | + |
| |
4 | 5 | ||
5 | 6 | ||
6 | - |
| |
7 | - |
| |
8 | - |
| |
9 | - |
| |
10 | 7 |
| |
11 | 8 |
| |
12 | 9 |
| |
13 | 10 |
| |
14 | 11 |
| |
15 | - |
| |
12 | + |
| |
13 | + |
| |
14 | + |
| |
15 | + |
|
Top-down DP
In essence, the DP top-down solution is the brute force solution with memoization. You may have noticed maxScore(l, r)
can be be memoized.
Letโs formalize our idea above by specifying our DP state (i.e. whatโs important that can lead us to our answer). In this case, let dp(l, r)
be the maximum score we can achieve if coins in the range [l, r]
are the only ones present and we go first.
Furthermore, our base case is: dp(l, r) = v_r
if l = r
. That is, since the range contains only one coin, we simply take that coin.
Now we deal with the transition. Exactly like our brute force solution, we consider two cases of picking either the left or right coin.
Next, we choose the case that gives us the greatest score or minimizes the opponent's score. Therefore, the solution is either:
dp(l, r) = max(sum(l, r) - dp(l + 1, r), sum(l, r) - dp(l, r - 1))
ordp(l, r) = sum(l, r) - min(dp(l + 1, r), dp(l, r - 1))
The following is a top-down solution to the problem:
1int max_score(vector<vector<int>> &dp, vector<int> &prefix_sum, int l, int r) {
2 if (dp[l][r] != 0) {
3 return dp[l][r];
4 }
5
6 int sum = prefix_sum[r] - prefix_sum[l - 1];
7 if (l == r) {
8 dp[l][r] = sum;
9 } else {
10 dp[l][r] = sum - min(max_score(dp, prefix_sum, l + 1, r), max_score(dp, prefix_sum, l, r - 1));
11 }
12
13 return dp[l][r];
14}
15
16int coin_game(vector<int> coins) {
17 int n = coins.size();
18 vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
19 vector<int> prefix_sum(n + 1, 0);
20 for (int i = 1; i <= n; i++) {
21 prefix_sum[i] = prefix_sum[i - 1] + coins[i - 1];
22 }
23 return max_score(dp, prefix_sum, 1, n);
24}
25
1public static int maxScore(int[][] dp, int[] prefixSum, int l, int r) {
2 if (dp[l][r] != 0) {
3 return dp[l][r];
4 }
5
6 int sum = prefixSum[r] - prefixSum[l - 1];
7 if (l == r) {
8 dp[l][r] = sum;
9 } else {
10 dp[l][r] = sum - Math.min(maxScore(dp, prefixSum, l + 1, r), maxScore(dp, prefixSum, l, r - 1));
11 }
12
13 return dp[l][r];
14}
15
16public static int coinGame(List<Integer> coins) {
17 int n = coins.size();
18 int[][] dp = new int[n + 1][n + 1];
19 int[] prefixSum = new int[n + 1];
20 prefixSum[0] = 0;
21 for (int i = 1; i <= n; i++) {
22 prefixSum[i] = prefixSum[i - 1] + coins.get(i - 1);
23 }
24 return maxScore(dp, prefixSum, 1, n);
25}
26
1function maxScore(dp, prefixSum, l, r) {
2 if (dp[l][r] != 0) {
3 return dp[l][r];
4 }
5
6 var sum = prefixSum[r] - prefixSum[l - 1];
7 if (l == r) {
8 dp[l][r] = sum;
9 } else {
10 dp[l][r] = sum - Math.min(maxScore(dp, prefixSum, l + 1, r), maxScore(dp, prefixSum, l, r - 1));
11 }
12
13 return dp[l][r];
14}
15
16function coinGame(coins) {
17 let n = coins.length;
18 var dp = new Array(n + 1);
19 for (let i = 0; i <= n; i++) {
20 dp[i] = new Array(n + 1);
21 for (let j = 0; j <= n; j++) {
22 dp[i][j] = 0;
23 }
24 }
25 var prefixSum = new Array(n + 1);
26 prefixSum[0] = 0;
27 for (let i = 1; i <= n; i++) {
28 prefixSum[i] = prefixSum[i - 1] + coins[i - 1];
29 }
30 return maxScore(dp, prefixSum, 1, n);
31}
32
1import sys
2sys.setrecursionlimit(1500)
3
4def max_score(dp, prefix_sum, l, r):
5 if dp[l][r] != 0:
6 return dp[l][r]
7
8 sum = prefix_sum[r] - prefix_sum[l - 1]
9 if l == r:
10 dp[l][r] = sum
11 else:
12 dp[l][r] = sum - min(max_score(dp, prefix_sum, l + 1, r), max_score(dp, prefix_sum, l, r - 1))
13
14 return dp[l][r]
15
16def coin_game(coins):
17 n = len(coins)
18 dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
19 prefix_sum = [0 for i in range(n + 1)]
20 for i in range(1, n + 1):
21 prefix_sum[i] = prefix_sum[i - 1] + coins[i - 1]
22 return max_score(dp, prefix_sum, 1, n)
23
Bottom-up DP
The iterative version is a bit trickier. The idea is that we loop through all the
possible lengths starting from 1 to n
. Then for each size, we consider all possible
left starting positions and calculate the respective right ending position. We do it in
this order because we are building solutions from the smallest case and building the
solutions up. That is, first considering each item as an interval of length 1 then
merging their solutions together to form larger and larger interval lengths until we get
to an interval of size n
.
Note: There are slight tweaks in the implementation of this idea such as how we loop through the lengths.
Here's a visualization of the table generated:
And here's the bottom-up iterative code:
1from typing import List
2
3def coin_game(coins: List[int]) -> int:
4 n = len(coins)
5 prefix_sum = [0 for i in range(n + 1)]
6 for i in range(1, n + 1):
7 prefix_sum[i] = prefix_sum[i - 1] + coins[i - 1]
8
9 dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
10 for size in range(0, n):
11 for l in range(1, n - size + 1):
12 r = l + size
13 if l == r:
14 dp[l][r] = prefix_sum[r] - prefix_sum[l - 1]
15 else:
16 dp[l][r] = prefix_sum[r] - prefix_sum[l - 1] - min(dp[l + 1][r], dp[l][r - 1])
17 return dp[1][n]
18
19if __name__ == '__main__':
20 coins = [int(x) for x in input().split()]
21 res = coin_game(coins)
22 print(res)
23
1import java.util.Arrays;
2import java.util.List;
3import java.util.Scanner;
4import java.util.stream.Collectors;
5
6class Solution {
7 public static int coinGame(List<Integer> coins) {
8 int n = coins.size();
9 int[] prefix_sum = new int[n + 1];
10 prefix_sum[0] = 0;
11 for (int i = 1; i <= n; i++) {
12 prefix_sum[i] = prefix_sum[i - 1] + coins.get(i - 1);
13 }
14
15 int[][] dp = new int[n + 1][n + 1];
16 for (int size = 0; size < n; size++) {
17 for (int l = 1; l + size <= n; l++) {
18 int r = l + size;
19 if (l == r) {
20 dp[l][r] = prefix_sum[r] - prefix_sum[l - 1];
21 } else {
22 dp[l][r] = prefix_sum[r] - prefix_sum[l - 1] - Math.min(dp[l + 1][r], dp[l][r - 1]);
23 }
24 }
25 }
26 return dp[1][n];
27 }
28
29 public static List<String> splitWords(String s) {
30 return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
31 }
32
33 public static void main(String[] args) {
34 Scanner scanner = new Scanner(System.in);
35 List<Integer> coins = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
36 scanner.close();
37 int res = coinGame(coins);
38 System.out.println(res);
39 }
40}
41
1function coinGame(coins) {
2 let n = coins.length;
3 var prefixSum = new Array(n + 1);
4 prefixSum[0] = 0;
5 for (let i = 1; i <= n; i++) {
6 prefixSum[i] = prefixSum[i - 1] + coins[i - 1];
7 }
8
9 var dp = new Array(n + 1);
10 for (let i = 0; i <= n; i++) {
11 dp[i] = new Array(n + 1);
12 for (let j = 0; j <= n; j++) {
13 dp[i][j] = 0;
14 }
15 }
16 for (let size = 0; size < n; size++) {
17 for (let l = 1; l + size <= n; l++) {
18 let r = l + size;
19 if (l == r) {
20 dp[l][r] = prefixSum[r] - prefixSum[l - 1];
21 } else {
22 dp[l][r] = prefixSum[r] - prefixSum[l - 1] - Math.min(dp[l + 1][r], dp[l][r - 1]);
23 }
24 }
25 }
26 return dp[1][n];
27}
28
29function splitWords(s) {
30 return s == "" ? [] : s.split(' ');
31}
32
33function* main() {
34 const coins = splitWords(yield).map((v) => parseInt(v));
35 const res = coinGame(coins);
36 console.log(res);
37}
38
39class EOFError extends Error {}
40{
41 const gen = main();
42 const next = (line) => gen.next(line).done && process.exit();
43 let buf = '';
44 next();
45 process.stdin.setEncoding('utf8');
46 process.stdin.on('data', (data) => {
47 const lines = (buf + data).split('\n');
48 buf = lines.pop();
49 lines.forEach(next);
50 });
51 process.stdin.on('end', () => {
52 buf && next(buf);
53 gen.throw(new EOFError());
54 });
55}
56
1#include <algorithm> // copy
2#include <iostream> // boolalpha, cin, cout
3#include <iterator> // back_inserter, istream_iterator
4#include <sstream> // istringstream
5#include <string> // getline, string
6#include <vector> // vector
7
8using namespace std;
9
10int coin_game(vector<int> coins) {
11 int n = coins.size();
12 vector<int> prefix_sum(n + 1, 0);
13 for (int i = 1; i <= n; i++) {
14 prefix_sum[i] = prefix_sum[i - 1] + coins[i - 1];
15 }
16
17 vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
18 for (int size = 0; size < n; size++) {
19 for (int l = 1; l + size <= n; l++) {
20 int r = l + size;
21 if (l == r) {
22 dp[l][r] = prefix_sum[r] - prefix_sum[l - 1];
23 } else {
24 dp[l][r] = prefix_sum[r] - prefix_sum[l - 1] - min(dp[l + 1][r], dp[l][r - 1]);
25 }
26 }
27 }
28 return dp[1][n];
29}
30
31template<typename T>
32std::vector<T> get_words() {
33 std::string line;
34 std::getline(std::cin, line);
35 std::istringstream ss{line};
36 ss >> std::boolalpha;
37 std::vector<T> v;
38 std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
39 return v;
40}
41
42int main() {
43 std::vector<int> coins = get_words<int>();
44 int res = coin_game(coins);
45 std::cout << res << '\n';
46}
47
Time Complexity: O(n^2)
for the nested for loops.
Space Complexity: O(n)
as we use a 2d dp
table.
Still not clear?ย Submitย the part you don't understand to our editors.