# My JAVA Solution from 60ms to 6ms with recursive and optimalize with dp thought

• first I use recursive to solve just easy to think

`````` /*recursive function each time we will either get left or get right but for one tag is make the result bigger
so assume the f(i, j) is the result that the number we will win with
each recursive is to get Max(nums[i]-f(i+1, j), nums[j]-f(i, j-1))*/
public boolean PredictTheWinner(int[] nums) {
return getRes(nums, 0, nums.length - 1) >= 0;
}
private int getRes(int[] nums, int l, int r) {
if (l == r) {
return nums[l];
}
return Math.max(nums[l] - getRes(nums, l + 1, r), nums[r] - getRes(nums, l, r - 1));
}
``````

but just beat 13% then I thought how to optimalize;we can see in program that the `getRes(nums, l + 1, r)` and `getRes(nums, l, r - 1)`for each recursive they should be calculate both ,so we can make a array `dp[i][j]`which record the form `l` to`r` data, and in this way we can avoid calculating repeatly ; this is program:

``````public boolean PredictTheWinner(int[] nums) {
int[][] dp = new int[nums.length][nums.length];
boolean[][] tag = new boolean[nums.length][nums.length];
return getRes(nums, 0, nums.length - 1, dp, tag) >= 0;
}

private int getRes(int[] nums, int l, int r, int[][] dp, boolean[][] tag) {
if (l == r) {
return nums[l];
}
if (tag[l][r]) {
return dp[l][r];
}
tag[l][r] = true;
dp[l][r] = Math.max(nums[l] - getRes(nums, l + 1, r, dp, tag), nums[r] - getRes(nums, l, r - 1,dp, tag));
return dp[l][r];
}
``````

6ms beat 80%

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.