记忆化搜索解决DP过程有效状态值稀疏的问题

字数统计: 5.5k字 | 阅读时长: 25分

2023-09-25

摘要: 最优子结构+重复子问题 -> 动态规划 -> 有很多对结果无影响的无效状态 -> 改为记忆化搜索

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

记忆化搜索是一种结合了搜索和动态规划的优点的算法。相应地，理解记忆化搜索算法就有搜索(递归)和动态规划两条路线。

（1）有时我们发现待解决的问题呈现出问题的解依赖于同一个问题的更小实例的解这样的特性，与递归的思想吻合。分析好子问题可以直接解决无需递归的情况，以及如何从子问题结果组装成原问题结果，就可以写出递归的算法解决问题了。但有时候会遇到子问题重复计算的情况，时间复杂度一般是指数型，此时可以开一个备忘录数组，记录子问题的解，形成记忆化搜索。

（2）有时我们发现待解决的问题除了问题的解依赖于同一个问题的更小实例的解这种递归特性，还进一步地有最优子结构和重复子问题的特性。此时我们就会直接考虑用动态规划解决，设计好状态，再列出状态转移方程就可以写出动态规划算法了。但是会遇到两个问题，一个是动态规划过程要遍历所有状态，而其中可能有一些是推出最终结果过程中始终没有用到的状态，用记忆化搜索就可以排除掉这些没有用到的状态，更进一步用搜索的话还有可能通过剪枝去掉大量无效状态；另一个是状态的设计、状态转移的方向，状态转移方程等动态规划的要素很多时候很难想，但是用搜索就很容易想，在搜索过程中用记忆化的方式把重复子问题做个记录，这就形成了类似于前面的（1）的思考路线。

总结一下，记忆化搜索可以理解为搜索的形式加上动态规划的思想，结合了搜索的容易想、可以避免对结果无影响的无效状态的计算、可能剪枝的好处，以及动态规划的避免重复子问题的好处。

从递归出发形成记忆化搜索的思考路径是：原问题的解依赖子问题的解 -> 先写出递归算法 -> 然后发现有很多重复子问题 -> 增加记忆化形成记忆化搜索算法。

从动态规划出发形成记忆化搜索的思考路径是：原问题呈现出最优子结构和重复子问题的特性 -> 先写出动态规划算法 -> 发现状态转移过程比较难想/有很多无效状态的计算 -> 改为记忆化搜索算法

本文我们给出一些 DP 过程有无效状态计算，也就是有效状态值比较稀疏，通过记忆化搜索可以减少对无效状态推导状态转移方程。

区间dp

546. 移除盒子

题解参考：【DP难题】力扣546-移除盒子

1563. 石子游戏 V

几块石子排成一行，每块石子都有一个关联值，关联值为整数，由数组 stoneValue 给出。

游戏中的每一轮：Alice 会将这行石子分成两个非空行（即，左侧行和右侧行）；Bob 负责计算每一行的值，即此行中所有石子的值的总和。Bob 会丢弃值最大的行，Alice 的得分为剩下那行的值（每轮累加）。如果两行的值相等，Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。

只剩下一块石子时，游戏结束。Alice 的分数最初为 0 。

返回 Alice 能够获得的最大分数。

提示：

1 2	1 <= stoneValue.length <= 500 1 <= stoneValue[i] <= 1e6

示例 1：
输入：stoneValue = [6,2,3,4,5,5]
输出：18
解释：在第一轮中，Alice 将行划分为 [6，2，3]，[4，5，5] 。左行的值是 11 ，右行的值是 14 。Bob 丢弃了右行，Alice 的分数现在是 11 。
在第二轮中，Alice 将行分成 [6]，[2，3] 。这一次 Bob 扔掉了左行，Alice 的分数变成了 16（11 + 5）。
最后一轮 Alice 只能将行分成 [2]，[3] 。Bob 扔掉右行，Alice 的分数现在是 18（16 + 2）。游戏结束，因为这行只剩下一块石头了。

示例 2：
输入：stoneValue = [7,7,7,7,7,7,7]
输出：28

示例 3：
输入：stoneValue = [4]
输出：0

代码 (C++)

class Solution {
public:
    int stoneGameV(vector<int>& stoneValue) {
        int n = stoneValue.size();
        dp = vector<vector<int>>(n, vector<int>(n, -1));
        vector<int> sums(n + 1, 0);
        for(int i = 1; i <= n; ++i)
            sums[i] = sums[i - 1] + stoneValue[i - 1];
        for(int i = 0; i < n; ++i)
        {
            dp[i][i] = 0;
        }
        return solve(0, n - 1, sums);
        return dp[0][n - 1];
    }

private:
    vector<vector<int>> dp;

    int solve(int i, int j, const vector<int>& sums)
    {
        if(dp[i][j] != -1)
            return dp[i][j];

        dp[i][j] = 0;
        for(int k = i; k < j; ++k)
        {
            int sum_l = sums[k + 1] - sums[i];
            int sum_r = sums[j + 1] - sums[k + 1];
            if(sum_l > sum_r)
            {
                dp[i][j] = max(solve(k + 1, j, sums) + sum_r, dp[i][j]);
            }
            else if(sum_l < sum_r)
            {
                dp[i][j] = max(solve(i, k, sums) + sum_l, dp[i][j]);
            }
            else
            {
                dp[i][j] = max(max(solve(i, k, sums), solve(k + 1, j, sums)) + sum_l, dp[i][j]);
            }
        }
        return dp[i][j];
    }
};

线性 dp

139. 单词拆分 / 140. 单词拆分 II / 472. 连接词

题解参考：单词拆分系列问题

688. “马”在棋盘上的概率

在一个 n x n 的国际象棋棋盘上，一个骑士从单元格 (row, column) 开始，并尝试进行 k 次移动。行和列是从 0 开始的，所以左上单元格是 (0,0) ，右下单元格是 (n - 1, n - 1) 。

象棋骑士有8种可能的走法，如下图所示。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格。

每次骑士要移动时，它都会随机从8种可能的移动中选择一种(即使棋子会离开棋盘)，然后移动到那里。

骑士继续移动，直到它走了 k 步或离开了棋盘。

返回骑士在棋盘停止移动后仍留在棋盘上的概率。

提示:

1
2
3

1 <= n <= 25
0 <= k <= 100
0 <= row, column <= n - 1

示例 1：
输入: n = 3, k = 2, row = 0, column = 0
输出: 0.0625
解释: 有两步(到(1,2)，(2,1))可以让骑士留在棋盘上。
在每一个位置上，也有两种移动可以让骑士留在棋盘上。
骑士留在棋盘上的总概率是0.0625。

示例 2：
输入: n = 1, k = 0, row = 0, column = 0
输出: 1.00000

算法：动态规划

状态定义 $dp[i][j][k]$ 表示以 $(i, j)$ 为起点，跳 $k$ 次，最终仍在棋盘上的概率。

状态转移方程为 $dp[i][j][k] = sum(1/8(dp[x][y][k - 1]))$，

代码 (C++)

class Solution {
public:
    int stoneGameV(vector<int>& stoneValue) {
        int n = stoneValue.size();
        dp = vector<vector<int>>(n, vector<int>(n, -1));
        vector<int> sums(n + 1, 0);
        for(int i = 1; i <= n; ++i)
            sums[i] = sums[i - 1] + stoneValue[i - 1];
        for(int i = 0; i < n; ++i)
        {
            dp[i][i] = 0;
        }
        return solve(0, n - 1, sums);
        return dp[0][n - 1];
    }

private:
    vector<vector<int>> dp;

    int solve(int i, int j, const vector<int>& sums)
    {
        if(dp[i][j] != -1)
            return dp[i][j];

        dp[i][j] = 0;
        for(int k = i; k < j; ++k)
        {
            int sum_l = sums[k + 1] - sums[i];
            int sum_r = sums[j + 1] - sums[k + 1];
            if(sum_l > sum_r)
            {
                dp[i][j] = max(solve(k + 1, j, sums) + sum_r, dp[i][j]);
            }
            else if(sum_l < sum_r)
            {
                dp[i][j] = max(solve(i, k, sums) + sum_l, dp[i][j]);
            }
            else
            {
                dp[i][j] = max(max(solve(i, k, sums), solve(k + 1, j, sums)) + sum_l, dp[i][j]);
            }
        }
        return dp[i][j];
    }
};

576. 出界的路径数

给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。你可以将球移到在四个方向上相邻的单元格内（可以穿过网格边界到达网格之外）。你最多可以移动 maxMove 次球。

给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。因为答案可能非常大，返回对 1e9 + 7 取余后的结果。

提示：

1 <= m, n <= 50
0 <= maxMove <= 50
0 <= startRow < m
0 <= startColumn < n

示例 1：
输入：m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
输出：6

示例 2：
输入：m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1
输出：12

算法：动态规划

矩阵线性 dp[i][j][k] + 记忆化

dp[i][j][k] := 位置 (i,j)，最多移动 k 次的答案
dp[i][j][k] = sum(dp[x][y][k - 1]) 其中 (x,y) 为与 (i,j) 相邻的四个新方向
初始化
if(i < 0 || i >= m || j < 0 || j >= n)
    return 1;
if(k == 0)
    return 0;

代码 (C++)

class Solution {
public:
    int findPaths(int m, int n, int N, int i, int j) {
        if(N == 0) return 0;
        // i, j, k: m, n, N
        vector<vector<vector<int> > > dp(m, vector<vector<int> >(n, vector<int>(N + 1, -1)));
        return dfs(i, j, m, n, N, dp);
    }

private:
    int MOD = 1e9 + 7;

    int dfs(int i, int j, int m, int n, int k, vector<vector<vector<int> > >& dp)
    {
        if(i < 0 || i >= m || j < 0 || j >= n)
            return 1;
        if(k == 0)
            return 0;
        if(dp[i][j][k] != -1)
            return dp[i][j][k];

        dp[i][j][k] = 0;
        int dx[4] = {0, 1, 0, -1};
        int dy[4] = {1, 0, -1, 0};
        for(int d = 0; d < 4; ++d)
        {
            int x = i + dx[d];
            int y = j + dy[d];
            dp[i][j][k] = (dp[i][j][k] + dfs(x, y, m, n, k - 1, dp)) % MOD;
        }
        return dp[i][j][k];
    }
};

代码 (Python)

import functools

MOD = int(1e9 + 7)

class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        self.m = m
        self.n = n
        self.dx = [0, 1, 0, -1]
        self.dy = [1, 0, -1, 0]
        if maxMove == 0:
            return 0
        return self.dfs(startRow, startColumn, maxMove)

    @functools.lru_cache(int(1e8))
    def dfs(self, i, j, k):
        if i < 0 or i >= self.m or j < 0 or j >= self.n:
            return 1
        if k == 0:
            return 0
        ans = 0
        for d in range(4):
            x = i + self.dx[d]
            y = j + self.dy[d]
            ans = (ans + self.dfs(x, y, k - 1)) % MOD
        return ans

514. 自由之路

电子游戏“辐射4”中，任务 “通向自由” 要求玩家到达名为 “Freedom Trail Ring” 的金属表盘，并使用表盘拼写特定关键词才能开门。

给定一个字符串 ring ，表示刻在外环上的编码；给定另一个字符串 key ，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。

最初，ring 的第一个字符与 12:00 方向对齐。您需要顺时针或逆时针旋转 ring 以使 key 的一个字符在 12:00 方向对齐，然后按下中心按钮，以此逐个拼写完 key 中的所有字符。

旋转 ring 拼出 key 字符 key[i] 的阶段中：

您可以将 ring 顺时针或逆时针旋转一个位置，计为1步。旋转的最终目的是将字符串 ring 的一个字符与 12:00 方向对齐，并且这个字符必须等于字符 key[i] 。
如果字符 key[i] 已经对齐到12:00方向，您需要按下中心按钮进行拼写，这也将算作 1 步。按完之后，您可以开始拼写 key 的下一个字符（下一阶段）, 直至完成所有拼写。

提示：

1
2
3

1 <= ring.length, key.length <= 100
ring 和 key 只包含小写英文字母
保证 字符串 key 一定可以由字符串  ring 旋转拼出

示例 1：
输入: ring = “godding”, key = “gd”
输出: 4
解释:
对于 key 的第一个字符 ‘g’，已经在正确的位置, 我们只需要1步来拼写这个字符。
对于 key 的第二个字符 ‘d’，我们需要逆时针旋转 ring “godding” 2步使它变成 “ddinggo”。
当然, 我们还需要1步进行拼写。
因此最终的输出是 4。

示例 2:
输入: ring = “godding”, key = “godding”
输出: 13

代码 (C++)

class Solution {
public:
    int findRotateSteps(string ring, string key) {
        int n = ring.size();
        vector<vector<int>> mapping(26); // ring 中 r -> idxs
        for(int i = 0; i < n; ++i)
        {
            mapping[ring[i] - 'a'].push_back(i);
        }

        // dp[i][j] := 当前在 key[i], ring[j] 的最少步数
        int m = key.size();
        vector<vector<int>> dp(n, vector<int>(m + 1, -1));
        for(int i = 0; i < n; ++i)
            dp[i][m] = 0;
        return solve(0, 0, key, ring, mapping, dp);
    }

private:
    int solve(int i, int j, const string& key, const string& ring, const vector<vector<int>>& mapping, vector<vector<int>>& dp)
    {
        if(dp[i][j] != -1) return dp[i][j];
        int n = ring.size();
        // 当前在 ring[i], 输入 key[j..m-1] 所需步数
        int ans = INT_MAX;
        for(int nxt: mapping[key[j] - 'a'])
        {
            int step = min((n + i - nxt) % n, (n + nxt - i) % n);
            ans = min(ans, step + 1 + solve(nxt, j + 1, key, ring, mapping, dp));
        }
        return dp[i][j] = ans;
    }
};

面试题 17.13. 恢复空格

哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子”I reset the computer. It still didn’t boot!”已经变成了”iresetthecomputeritstilldidntboot”。在处理标点符号和大小写之前，你得先把它断成词语。当然了，你有一本厚厚的词典dictionary，不过，有些词没在词典里。假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。

注意：本题相对原题稍作改动，只需返回未识别的字符数

提示：

1
2
3

0 <= len(sentence) <= 1000
dictionary中总字符数不超过 150000。
你可以认为dictionary和sentence中只包含小写字母。

示例：
输入：
dictionary = [“looked”,”just”,”like”,”her”,”brother”]
sentence = “jesslookedjustliketimherbrother”
输出： 7
解释：断句后为”jess looked just like tim her brother”，共7个未识别字符。

代码 (C++)

class Solution {
public:
    int respace(vector<string>& dictionary, string sentence) {
        for(const string& word: dictionary)
        {
            int len = word.size();
            lens.insert(len);
            words.insert(word);
        }
        int n = sentence.size();
        vector<int> dp(n, -1);
        return dfs(0, sentence, dp);
    }

private:
    set<int> lens;
    unordered_set<string> words;

    int dfs(int pos, const string& s, vector<int>& dp)
    {
        int n = dp.size();
        if(pos == n) return 0;
        if(dp[pos] != -1) return dp[pos];

        dp[pos] = n - pos;

        for(int l: lens)
        {
            string cur = s.substr(pos, l);
            if(words.count(cur) == 0)
                continue;
            if(pos + l > n) continue;
            dp[pos] = min(dp[pos], dfs(pos + l, s, dp));
        }
        if(pos < n)
            dp[pos] = min(dp[pos], 1 + dfs(pos + 1, s, dp));
        return dp[pos];
    }
};

状态压缩DP

980. 不同路径 III

题解参考：哈密顿路径

638. 大礼包

在 LeetCode 商店中，有 n 件在售的物品。每件物品都有对应的价格。然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。

给你一个整数数组 price 表示物品价格，其中 price[i] 是第 i 件物品的价格。另有一个整数数组 needs 表示购物清单，其中 needs[i] 是需要购买第 i 件物品的数量。

还有一个数组 special 表示大礼包，special[i] 的长度为 n + 1 ，其中 special[i][j] 表示第 i 个大礼包中内含第 j 件物品的数量，且 special[i][n] （也就是数组中的最后一个整数）为第 i 个大礼包的价格。

返回确切满足购物清单所需花费的最低价格，你可以充分利用大礼包的优惠活动。你不能购买超出购物清单指定数量的物品，即使那样会降低整体价格。任意大礼包可无限次购买。

提示：

n == price.length
n == needs.length
1 <= n <= 6
0 <= price[i] <= 10
0 <= needs[i] <= 10
1 <= special.length <= 100
special[i].length == n + 1
0 <= special[i][j] <= 50

示例 1：
输入：price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2]
输出：14
解释：有 A 和 B 两种物品，价格分别为 ¥2 和 ¥5 。
大礼包 1 ，你可以以 ¥5 的价格购买 3A 和 0B 。
大礼包 2 ，你可以以 ¥10 的价格购买 1A 和 2B 。
需要购买 3 个 A 和 2 个 B ，所以付 ¥10 购买 1A 和 2B（大礼包 2），以及 ¥4 购买 2A 。

示例 2：
输入：price = [2,3,4], special = [[1,1,0,4],[2,2,1,9]], needs = [1,2,1]
输出：11
解释：A ，B ，C 的价格分别为 ¥2 ，¥3 ，¥4 。
可以用 ¥4 购买 1A 和 1B ，也可以用 ¥9 购买 2A ，2B 和 1C 。
需要买 1A ，2B 和 1C ，所以付 ¥4 买 1A 和 1B（大礼包 1），以及 ¥3 购买 1B ， ¥4 购买 1C 。
不可以购买超出待购清单的物品，尽管购买大礼包 2 更加便宜。

代码 (C++)

class Solution {
public:
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        if(needs.empty()) return 0;
        int n = needs.size();
        // state 需要 3 * n 位
        // n == 2
        // 000111111 (1 << (n * 3))
        vector<int> dp((1 << (n * 3)), -1);
        dp[0] = 0;
        unordered_map<int, int> valid;
        for(int i = 0; i < n; ++i)
            valid[(1 << (i * 3))] = price[i];
        for(const vector<int>& bag: special)
        {
            int val = bag[n];
            int state = 0;
            for(int i = 0; i < n; ++i)
            {
                int item_state = bag[i]; // 0 ~ 6
                state |= (item_state << (i * 3));
            }
            if(valid.count(state) == 0)
                valid[state] = val;
            else
                valid[state] = min(valid[state], val);
        }
        int target_state = 0;
        for(int i = 0; i < n; ++i)
        {
            int item_state = needs[i];
            target_state |= (item_state << (i * 3));
        }
        return solve(target_state, valid, dp, n);
    }

private:
    int solve(int state, unordered_map<int, int>& valid, vector<int>& dp, int n)
    {
        if(dp[state] != -1)
            return dp[state];

        dp[state] = INT_MAX;
        for(pair<int, int> select: valid)
        {
            int s = select.first;
            int nxt = next_state(state, s, n);
            if(nxt == -1) continue;
            int val = select.second;
                dp[state] = min(dp[state], val + solve(nxt, valid, dp, n));
        }
        return dp[state];
    }

    int next_state(int state, int cur, int n)
    {
        for(int i = 0; i < n; ++i)
        {
            // 000...00111 向右整体移 i * 3 位
            int cnt1 = (7 << i * 3) & state;
            int cnt2 = (7 << (i * 3)) & cur;
            if(cnt1 < cnt2)
                return -1;
        }
        return state - cur;
    }
};

351. 安卓系统手势解锁

我们都知道安卓有个手势解锁的界面，是一个 3 x 3 的点所绘制出来的网格。用户可以设置一个 “解锁模式” ，通过连接特定序列中的点，形成一系列彼此连接的线段，每个线段的端点都是序列中两个连续的点。如果满足以下两个条件，则 k 点序列是有效的解锁模式：

解锁模式中的所有点互不相同。
假如模式中两个连续点的线段需要经过其他点的中心，那么要经过的点必须提前出现在序列中（已经经过），不能跨过任何还未被经过的点。
- 例如，点 5 或 6 没有提前出现的情况下连接点 2 和 9 是有效的，因为从点 2 到点 9 的线没有穿过点 5 或 6 的中心。
- 然而，点 2 没有提前出现的情况下连接点 1 和 3 是无效的，因为从圆点 1 到圆点 3 的直线穿过圆点 2 的中心。

以下是一些有效和无效解锁模式的示例：

无效手势：[4,1,3,6] ，连接点 1 和点 3 时经过了未被连接过的 2 号点。
无效手势：[4,1,9,2] ，连接点 1 和点 9 时经过了未被连接过的 5 号点。
有效手势：[2,4,1,3,6] ，连接点 1 和点 3 是有效的，因为虽然它经过了点 2 ，但是点 2 在该手势中之前已经被连过了。
有效手势：[6,5,4,1,9,2] ，连接点 1 和点 9 是有效的，因为虽然它经过了按键 5 ，但是点 5 在该手势中之前已经被连过了。

给你两个整数，分别为 m 和 n ，那么请返回有多少种不同且有效的解锁模式，是至少需要经过 m 个点，但是不超过 n 个点的。

两个解锁模式不同需满足：经过的点不同或者经过点的顺序不同。

提示：

1	1 <= m, n <= 9

示例 1：
输入：m = 1, n = 1
输出：9
示例 2：
输入：m = 1, n = 2
输出：65

算法：动态规划

状态定义 $dp[state][i]$ 表示当前已经选则的集合为 state, 当前位置在 i 时，

代码 (C++)

class Solution {
public:
    int numberOfPatterns(int m, int n) {
        int result = 0;
        int state = 0;
        for(int i = 1; i <= 9; ++i)
            dfs((state | (1 << (i - 1))), i, result, n, m, 1);
        return result;
    }

private:

    void dfs(int state, int cur, int& result, int n, int m, int num)
    {
        if(num > n)
            return;
        if(num >= m)
            ++result;
        for(int i = 1; i <= 9; ++i)
        {
            if(state & (1 << (i - 1)))
                continue;
            if(!_check(state, cur, i))
                continue;
            dfs((state | (1 << (i - 1))), i, result, n, m, num + 1);
        }
    }

    bool _check(int state, int i, int j)
    {
        if(i == 1 && j == 3) return (state & (1 << 1));
        if(i == 3 && j == 1) return (state & (1 << 1));
        if(i == 1 && j == 7) return (state & (1 << 3));
        if(i == 7 && j == 1) return (state & (1 << 3));
        if(i == 3 && j == 9) return (state & (1 << 5));
        if(i == 9 && j == 3) return (state & (1 << 5));
        if(i == 7 && j == 9) return (state & (1 << 7));
        if(i == 9 && j == 7) return (state & (1 << 7));
        if(i == 2 && j == 8) return (state & (1 << 4));
        if(i == 8 && j == 2) return (state & (1 << 4));
        if(i == 4 && j == 6) return (state & (1 << 4));
        if(i == 6 && j == 4) return (state & (1 << 4));
        if(i == 1 && j == 9) return (state & (1 << 4));
        if(i == 9 && j == 1) return (state & (1 << 4));
        if(i == 3 && j == 7) return (state & (1 << 4));
        if(i == 7 && j == 3) return (state & (1 << 4));
        return true;
    }
};

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法搜索

记忆化搜索解决DP过程有效状态值稀疏的问题

区间dp

546. 移除盒子

1563. 石子游戏 V

代码 (C++)

线性 dp

139. 单词拆分 / 140. 单词拆分 II / 472. 连接词

688. “马”在棋盘上的概率

算法：动态规划

代码 (C++)

576. 出界的路径数

算法：动态规划

代码 (C++)

代码 (Python)

514. 自由之路

代码 (C++)

面试题 17.13. 恢复空格

代码 (C++)

状态压缩DP

980. 不同路径 III

638. 大礼包

代码 (C++)

351. 安卓系统手势解锁

算法：动态规划

代码 (C++)