记忆化搜索

互动

记忆化搜索复杂度分析

多少种组合*每层耗费

记忆化搜索 = 分治 + hashmap

会变化的参数放在hashmap里

函数的限制：

1. 要有返回值（DC）

   和Cache很像

2. 函数的结果，只与输入的参数有关，与其他信息无关

   叫做pure function（类似前端的纯函数，与其他全局变量无关）

重复计算

记忆化搜索 = 动态规划

（只是说是用搜索的方式实现的DP）

博弈问题非常适合记忆化搜索

boolean memoSearch(int n, Map<Integer, Boolean> memo) {
    if (n < 3) {
        return true;
    }
    if(memo.containsKey(n)) {
        return memo.get(n);
    }
    
    for (int i = 1; i <= 3; i++) {
        if (!memoSearch(n - i, memo)) {
            memo.put(n, true);
            return true;
        }
    }
    return false;
}

问题：会栈溢出

如果时间复杂度和递归深度都是On级别时，会栈溢出

如果时间复杂度On2、递归深度都是On级别时，就不会

记忆化搜索的缺点：不适合解决时间复杂度On的DP问题，有栈溢出的风险

记忆化搜索，模式简单，就在搜索上加几行代码

循环DP需要考虑循环先后顺序的问题