forked from gouthampradhan/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathStoneGame.java
More file actions
101 lines (97 loc) · 3.58 KB
/
Copy pathStoneGame.java
File metadata and controls
101 lines (97 loc) · 3.58 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
package dynamic_programming;
import java.util.*;
/**
* Created by gouthamvidyapradhan on 22/03/2019
* Alex and Lee play a game with piles of stones. There are an even number of piles arranged in a row, and each
* pile has a positive integer number of stones piles[i].
*
* The objective of the game is to end with the most stones. The total number of stones is odd, so there are no ties.
*
* Alex and Lee take turns, with Alex starting first. Each turn, a player takes the entire pile of stones from
* either the beginning or the end of the row. This continues until there are no more piles left, at which point
* the person with the most stones wins.
*
* Assuming Alex and Lee play optimally, return True if and only if Alex wins the game.
*
*
*
* Example 1:
*
* Input: [5,3,4,5]
* Output: true
* Explanation:
* Alex starts first, and can only take the first 5 or the last 5.
* Say he takes the first 5, so that the row becomes [3, 4, 5].
* If Lee takes 3, then the board is [4, 5], and Alex takes 5 to win with 10 points.
* If Lee takes the last 5, then the board is [3, 4], and Alex takes 4 to win with 9 points.
* This demonstrated that taking the first 5 was a winning move for Alex, so we return true.
*
*
* Note:
*
* 2 <= piles.length <= 500
* piles.length is even.
* 1 <= piles[i] <= 500
* sum(piles) is odd.
*
* Solution:
* O(N ^ 2)
* Each state can be considered as State = (total stones left, player's turn). Do a dfs on each state and memoize
* the result in order not to recalculate. When all the stones are exhausted - Alex wins if the total collected stones
* by her is greater than total collected by Lee
*/
public class StoneGame {
/**
* Main method
* @param args
*/
public static void main(String[] args) {
int[] A = {5,3,4,5};
System.out.println(new StoneGame().stoneGame(A));
}
public boolean stoneGame(int[] piles) {
int sum = 0;
for(int i = 0; i < piles.length; i ++){
sum += piles[i];
}
int[][] A = new int[2][sum + 1];
Arrays.fill(A[0], -1);
Arrays.fill(A[1], -1);
int result = dp(A, piles, 0, piles.length - 1, sum, 0, 0, 0);
return result == 1;
}
private int dp(int[][] A, int[] piles, int i, int j, int sum, int p, int sumA, int sumB){
if(A[p][sum] != -1) return A[p][sum];
else {
if(p == 0){
if(i <= j){
int result = dp(A, piles, i + 1, j, sum - piles[i], (p + 1) % 2, sumA + piles[i], sumB);
if(result == 0){
A[p][sum] = 1;
return 1;
} else {
result = dp(A, piles, i, j - 1, sum - piles[j], (p + 1) % 2, sumA + piles[j], sumB);
A[p][sum] = result;
return result;
}
} else{
if(sumA > sumB) return 1; else return 0;
}
} else {
if(i <= j){
int result = dp(A, piles, i + 1, j, sum - piles[i], (p + 1) % 2, sumA, sumB + piles[i]);
if(result == 0){
A[p][sum] = 1;
return 1;
} else {
result = dp(A, piles, i, j - 1, sum - piles[j], (p + 1) % 2, sumA, sumB + piles[j]);
A[p][sum] = result;
return result;
}
} else{
if(sumB > sumA) return 1; else return 0;
}
}
}
}
}