记忆化搜索

——从深度优先搜索过渡到动态规划
记忆化搜索是动态规划的一种实现方式，记忆化搜索使用搜索的方式实现了动态规划，因此记忆化搜索就是动态规划。
将函数的计算结果保存下来，下次通过同样的参数访问时，直接返回保存下来的结果。
记忆化搜索通常能够将指数级别的时间复杂度降低到多项式级别。
跟系统设计中的cache(缓存)很像，第一次浏览图片的时候需要加载出来，然后系统会将图片加载到缓存中，之后浏览图片的时候就不需要加载了。
动态规划避免了重复计算，因此动态规划速度很快。
记忆化搜索非常适合博弈型动态规划。

//一共有n个石头，两人轮番拿1~3个，拿到最后一个的赢，请判断是否先手必赢
bool canWinBash(int n)
{
    unordered_map<int, bool> memo;
    return memoSearch(n, memo);
}
bool memoSearch(int n, unordered_map<int, bool> memo)
{
    if (n <= 3)
    {
        return true;
    }
    if (memo.find(n) != memo.end())
    {
        return memo[n];
    }
    for (int i = 1; i <= 3; i++)
    {
        if (!memoSearch(n - i, memo))
        {
            memo.insert({n, true});
            return true;
        }
    }
    return false;
}

通配符匹配

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。

‘?’ 可以匹配任何单个字符。
‘*’ 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。

思路