什么时候用记忆搜索 初始状态不好找

博奕

375. Guess Number Higher or Lower II

怎么找递推？对于这种并没有给出数组或者是String的该怎么办

Local Max Global Min的问题 中间的每一步取最坏情况计算 然后最终的结果建立在这个基础上取最小 有点像划分动规 只是原始的模型不是很好想出来 比如猜测(1,n)之间的数所得到的最小值是什么

memo[i][j]: the minimum number of money should require if guessing between [i , j]

由于我们需要 “保证得到结果”，也就是说对于指定 k 的选择，我们需要准备最坏情况 cost 是以下三种结果生成的 subproblem 中cost 最大的那个； 然而同时对于一个指定区间 [i , j] ，我们可以选择任意 i <= k <= j ，对于这个 k 的主观选择可以由我们自行决定，我们要选的是 k s.t. 其子问题的 cost + 当前操作 cost 最小的一个，至此，每次决策就构成了一次 MiniMax 的博弈。+

又是可以把长度当作循环最外层

public class Solution {
    public int getMoneyAmount(int n) {
        int[][] memo = new int[n+1][n+1];
        //以left和right的间距作为循环变量
        for(int len = 1;len <= n;len++){
            for(int left = 1;left <= n-len;left++){
                int right = left + len;
                //首先将要求的填补为最大，不至于在第一轮就选0
                memo[left][right] = Integer.MAX_VALUE;
                //choose the first element to guess
                for(int i = left;i < right;i++){
                    memo[left][right] = Math.min(memo[left][right],i+Math.max(memo[left][i-1],memo[i+1][right]));
                }
            }
        }
        return memo[1][n];
    }
}

Coins in a Line

A能赢的情况是A下完钱币的局面对于B来说有一场是输的就行 所以定义dp[i]为对于当前出钱币的人是否会输赢 每次下棋后只会有两种结果

public class Solution {
    /**
     * @param n: an integer
     * @return: a boolean which equals to true if the first player will win
     */
    public boolean firstWillWin(int n) {
        //base case
        if(n == 0)return false;
        if(n <= 2)return true;
        //whether a starting number of n element for game player1 win
        boolean[] dp = new boolean[n + 1];
        dp[0] = false;
        dp[1] = true;
        dp[2] = true;
        for(int i = 3;i <= n;i++){
            if((!dp[i-1])||(!(dp[i-2]))){
                dp[i] = true;
            }
        }
        return dp[n];
    }
}

Coins in a Line II

这次比的是谁拿的coins sum value最大 当当前选手能拿到的最大值大于一半的value总和时返回True

同样的用DP(i)表示还有i个硬币时当前选手可以获得的最大值

怎么决定DP(i)取决于DP(i-1)和DP(i-2)哪个大 而DP(i-1)所取的是对手所给的可能情况的最小值 又是一个外取Max 内取小的问题

public class Solution {
    /**
     * @param values: an array of integers
     * @return: a boolean which equals to true if the first player will win
     */
    public boolean firstWillWin(int[] values) {
        // write your code here
        int n = values.length;
        if(n <= 2)return true;
        int[] dp = new int[n + 1];
        int sum = 0;
        for(int i = 0;i < n;i++){
            sum += values[i];
        }
        Arrays.fill(dp, -1);
        dp[0] = 0;
        dp[1] = values[n - 1];
        dp[2] = values[n - 1] + values[n - 2];

        int val = memoizedSearch(n,values,dp);
        if(val*2 > sum)return true;
        return false;
    }
    private int memoizedSearch(int coins, int[] values, int[] dp){
        if(coins < 0) return 0;
        //has been computed before 
        if(dp[coins] != -1) return dp[coins];
        int n = values.length;

        int oneMax = values[n - coins] + Math.min(memoizedSearch(coins - 2, values, dp), memoizedSearch(coins - 3, values, dp));

        int twoMax = values[n - coins] + values[n - coins + 1] 
                     + Math.min(memoizedSearch(coins - 3, values, dp), 
                                memoizedSearch(coins - 4, values, dp));

        dp[coins] = Math.max(oneMax, twoMax);
        return dp[coins];
    }
}

Coins in a Line III

区间 + Memo Search 方法还是画决策树 定义二维dp dp[i][j] 现在还第i到第j的硬币，现在先手取硬币的人最后最多取硬币价值

这次 左边和右边都可以取 每次取一个

Use boolean array to track whether the situation is calculated before and perform memo search

Time: O(N2)

294. Flip Game II

记忆化搜索 A开始玩可以赢的条件是A 下完的任何一种棋盘 B赢不了

用来判断第一个人先下棋是否会赢的函数可以重复使用 回溯的思想里就是第一个人下完棋剩下的棋局对于第二个人必输 也就是再次使用函数返回

false有一个返回false 只要返回false则最终结果返回true。为了加快速度 用HashMap存取中间出现过的棋盘所对应的结果

String.startsWith(String,index)

public class Solution {
    /** We can traverse all the possible ways of placing “--” and we keep track of the player's step
     * If there is a way of winning then return true
     * The minimum steps to reach the state without continuous "++". If it's odd then return true*/
    public boolean canWin(String s) {
        if(s==null||s.length()<2)return false;
        HashMap<String,Boolean> map = new HashMap<String,Boolean>();
        return helper(s,map);
    }
    //use a HashMap to maintains the string already visited and save the time
    public boolean helper(String s,HashMap<String,Boolean>map){
        if(map.containsKey(s))return map.get(s);
        int len = s.length();
        for(int i = 0;i < len-1;i++){
            if (s.startsWith("++", i)) {
                String t = s.substring(0,i)+"--"+s.substring(i+2);
                if(!helper(t, map)){
                    map.put(s,true);
                    return true;
                }
            }
        }
        map.put(s,false);
        return false;
    }
}