publicclassSolution { /** * @param n: an integer * @return: a boolean which equals to true if the first player will win */publicbooleanfirstWillWin(int n) {// write your code hereif(n ==0) returnfalse;if(n <=2) returntrue;boolean[] dp =newboolean[n +1]; dp[0] =false; dp[1] =true; dp[2] =true;for(int i =3; i <= n; i++){ dp[i] = (!dp[i -1]) || (!dp[i -2]); }return dp[n]; }}
dp[start][end] 当前玩家从index = (start, end) 区间内的最大 value
除此之外题目的结构和记忆化搜索并没有太大区别,依然是 MiniMax + Memoization.
ps: 假设没有面值为 0 的硬币,相比上一题跳过了 Arrays.fill -1 的初始化。
publicclassSolution { /** * @param values: an array of integers * @return: a boolean which equals to true if the first player will win */publicbooleanfirstWillWin(int[] values) {// write your code hereint n =values.length;if(n <=1) returntrue;// dp[i][j] = maximum value current player can get// between start = i, end = jint[][] dp =newint[n][n]; dp[0][0] = values[0]; dp[n -1][n -1] = values[n -1];int sum =0;for(int num : values){ sum += num; }return2*memoizedSearch(0, n -1, values, dp)> sum; }privateintmemoizedSearch(int start,int end,int[] values,int[][] dp){if(start > end) return0;if(dp[start][end] !=0) return dp[start][end];int takeLeft = values[start] +Math.min(memoizedSearch(start +2, end, values, dp),memoizedSearch(start +1, end -1, values, dp));int takeRight = values[end] +Math.min(memoizedSearch(start +1, end -1, values, dp),memoizedSearch(start, end -2, values, dp)); dp[start][end] =Math.max(takeLeft, takeRight);return dp[start][end]; } }