RefDash_GetOptimalMove [source code]

public class RefDash_GetOptimalMove {
static
/****************************************************************************/
class Solution {
    Map<Integer, Integer> memo = new HashMap<> ();

    int getOptimalMove(int current_state) {
        if (memo.containsKey (current_state)) {
            return memo.get (current_state);
        }
        int upper = (int) Math.sqrt (current_state);
        int res = -1;
        for (int i = 1; i <= upper; i++) {
            int your_state = getOptimalMove (current_state - i * i);
            if (your_state < 0) {
                res = i * i;
                break;
            }            
        }
        memo.put (current_state, res);
        return res;
    }
}
/****************************************************************************/

    public static void main(String[] args) {
        RefDash_GetOptimalMove.Solution tester = new RefDash_GetOptimalMove.Solution();
    }
}

题目比较简单, 拿到一个state, 然后只能够减去一个perfect square, 然后题目要求就是要你返回, 比如我拿到了50, 我应该减去多少才能够赢. 如果你拿到一个数字, 是0, 就输了. 注意比0大的都有可能能赢, 因为1也是一个perfect square, 所以还可以继续减, 然后丢回去给对手;

最后题目还是比较简单的, 大概分析了一下, 很快代码写完, 然后加上一个memo; 最后也问了复杂度, 是NsqrtN, 这个可能要结合例子来看:

50: 1..7  
    1: 1  
    ..  
    49: 1..7

这样一个例子一写出来, 复杂度的规律就比较容易看出来了, 因为看这里, 一个level只减少了1, 所以最多可以有N的height, 然后每一个level的fanout是sqrtN, 最后就不难分析了; 用例子来帮助分析好很多;

当然另外一种方法你可能说用aggregate来分析, 实际上加了memo之后好像是可以, 还是一样的啊, 1..50的每一个数字, 都有sqrtN个可能的类似 sub num的概念, 所以最后稍微宽松一点的bound还是要走到NsqrtN.

另外这里一个我miss掉的优化, 就是循环最好从大的开始走, 因为这样我们其实在tree里面是优先走比较短的path, 这个有点类似fail fast的思想.

Problem Description