1300 · Bash Game [LintCode]

一刷 06/2022

Version #1 DP

思路是dp[i - 1], dp[i - 2], dp[i - 3]是对手可以选择的结果，只要保证对手的结果里面存在着false，我方就一定会取那个对手是false的解

Time O(N)

Space O(1)

public class Solution {

/**

* @param n: an integer

* @return: whether you can win the game given the number of stones in the heap

*/

public boolean canWinBash(int n) {

// Write your code here

// dp[n] == true, iff dp[n - 1] == false, dp[n - 2] == false, dp[n - 3] == false

boolean[] dp = new boolean[4];

for (int i = 0; i <= 2 && i < n; i++) {

dp[i] = true;

}

for (int i = 3; i < n; i++) {

if (!dp[(i - 1) % 4] || !dp[(i - 2) % 4] || !dp[(i - 3) % 4]) {

dp[i % 4] = true;

}

}

return dp[(n - 1) % 4];

}

}