来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/edit-distance

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

1. 插入一个字符
2. 删除一个字符
3. 替换一个字符

示例 1：

• 输入：word1 = "horse", word2 = "ros"
• 输出：3

• 解释：

  horse -> rorse (将 'h' 替换为 'r')
  rorse -> rose (删除 'r')
  rose -> ros (删除 'e')

示例 2：

• 输入：word1 = "intention", word2 = "execution"
• 输出：5

• 解释：

  intention -> inention (删除 't')
  inention -> enention (将 'i' 替换为 'e')
  enention -> exention (将 'n' 替换为 'x')
  exention -> exection (将 'n' 替换为 'c')
  exection -> execution (插入 'u')

二、题目解析

这道题目和leetcode44-通配符匹配很类似，比较两个字符串之间的状态，因此也可以使用相同的办法。

以dp[i][j]表示word1的第i个字符到word2的第j字符转换需要的最小操作数，动态转移方程可以表示为：

$$\begin{equation} dp[i][j]= \begin{cases} dp[i-1][j-1] & word1[i]=word2[j]\\ min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 & word1[i] \ne word2[j]\end{cases} \end{equation}$$

说明：如果word1[i]和word2[j]相等，那么最小操作次数就等于dp[i-1][j-1]。如果不相等，那么操作次数就应该是两个字符串的前一个字符匹配结果中的最小值加一。

三、代码

static inline int min(int x, int y) {
    return x < y ? x : y;
}

class Solution {
public:
    int minDistance(string word1, string word2) {
        int i, j, row, col;
        vector<vector<int>> dp;

        if (word1.empty() || word2.empty())
            return word1.size() + word2.size();

        row = word1.size();
        col = word2.size();
        dp.reserve(row + 1);

        for (i = 0; i <= row; i++) {
            dp.emplace_back();
            vector<int> &v = dp[i];
            dp[i].reserve(col + 1);
            for (j = 0; j <= col; j++) {
                if (j == 0) {
                    dp[i].push_back(i);
                } else if (i == 0) {
                    dp[i].push_back(j);
                } else {
                    dp[i].push_back(0);
                }
            }
        }

        for (i = 1; i <= word1.size(); i++) {
            for (j = 1; j <= word2.size(); j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        return dp[row][col];
    }
};

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/super-egg-drop

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。

每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。

你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。

每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。

你的目标是确切地知道 F 的值是多少。无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？

示例 1：

• 输入：K = 1, N = 2
• 输出：2
• 解释：鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。如果它没碎，那么我们肯定知道 F = 2 。因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。

示例 2：

• 输入：K = 2, N = 6
• 输出：3

示例 3：

• 输入：K = 3, N = 14
• 输出：4

提示：

• 1 <= K <= 100
• 1 <= N <= 10000

二、动态规划+递归

看到题目的第一眼就能想到得用动态规划来解题了，关键是如何来定义动态规划的状态和状态转移方程。

比较容易想到的是以dp(k, n)来表示k个鸡蛋在n层建筑时需要扔鸡蛋的最小次数，它的最优状态肯定是从前面的1-n层楼中取，谁的状态越优，就取谁的。也就是说，在那一层扔鸡蛋需要的次数最少，就是谁。那么：

$$dp(k,n)=min(dp(k,1), dp(k,2), ..., dp(k,n))$$

在第i层扔鸡蛋，有两种结果：

1. 鸡蛋碎了，这个时候鸡蛋少了一个，楼层也少一个，此时它的最优解是dp(k-1,i-1) + 1。
2. 鸡蛋没碎，这个时候鸡蛋没少，楼层少了一个，最优解是dp(k,n-i) + 1。

可以参考这张图片：

图片来源：labuladong

后面的dp[k][n]和dp(k, n)是一个意思。

为什么没碎之后是dp[k][n-i]，因为没碎的话，鸡蛋还是k个，而楼层只有n-i了，所以只要找出dp[k][n-i]就可以了。

计算出来这两种情况后，要选择最坏情况下的场景，所以要取两者的最大值。总结出来状态转移方程就是：

$$\begin{equation} dp[k][i]= \begin{cases} 1 & k=1 \\ 0 & n=0\\ max(dp[k-1][i-1], dp[k][n-i]) & k>1,n>0 \end{cases}\end{equation}$$

归纳成C++代码：

int dp(int k, int n, vector<vector<int>> &v) {
    int i, f = INT_MAX, dpi;
    
    if (k == 1) return n;
    if (n == 0) return 0;

    // v数组默认全是-1
    if (v[k][n] != -1) {
        return v[k][n];
    }

    // 遍历所有楼层
    for (i = 1; i <= n; i++) {
        // 计算出第i层的最优解
        dpi = max(dp(k - 1, i - 1, v), dp(k, n - i, v)) + 1;
        // 计算所有楼层的最小值
        f = min(f, dpi);
    }

    v[k][n] = f;
    return f;
}

时间复杂度

计算所有的鸡蛋+楼层组合需要时间复杂度O(KN)，每个楼层取最优值是O(N)，总体的时间复杂度是：

$$O(K*N^2)$$

这个时间复杂度还是很大的，可以说迄今为止我还没见过这么高复杂度的动态规划。提交后果然超时了：

在本地测试这组数据发现需要执行2s+才能计算出来（CPU是I5-8400主频2.8GHz），所以提交肯定会超时：

三、动态规划+二分

超时之后不得不想办法优化，优化前为了确定在哪个楼层扔鸡蛋最优不得不从1遍历到n，这个时间复杂度是O(N)太长了，实际上可以使用二分法来找出最优解，讲O(N)变成O(logN)。

上面已经求出了状态转移方程是max(dp[k-1][i-1], dp[k][n-i])，其中可以知道的是，dp[k-1][i-1]是随着i逐步递增的，因为楼层越高，需要扔的次数肯定也越多。而dp[k][n-i]是跟随i递减的，因子i是负数，i越大，n-i越小，扔的次数也越小。

上面的状态转移方程就是现在所有楼层的最大值中，找到最小值，如图所示：

红色的线表示的是两个子状态中的最大值，两根线的交点正好就是所有最大值中的最小值。那么根据这个规律，就可以把i∈[1, n]的遍历改成二分法来遍历，找到这个最小值。代码如下：

int dp(int k, int n, vector<vector<int>> &v) {
    int i, f = INT_MAX;
    int low, high, mid, broken, not_broken;
    
    if (k == 1) return n;
    if (n == 0) return 0;

    if (v[k][n] != -1) {
        return v[k][n];
    }

    low = 1;
    high = n;
    while (low <= high) {
        mid = (low + high) / 2;
        // 鸡蛋碎了
        broken = dp(k - 1, mid - 1, v);
        // 鸡蛋没碎
        not_broken = dp(k, n - mid, v);
        if (broken > not_broken) {
            high = mid - 1;
            f = min(f, broken + 1);
        } else {
            low = mid + 1;
            f = min(f, not_broken + 1);
        }
    }
    
    v[k][n] = f;
    return f;
}

修改后再测试上面超时的数据，只要4毫秒就可以执行完了，效率提高了几百倍：

再次提交代码，通过了（耗时较高）：

把遍历变成二分后，遍历的O(N)变成了O(logN)，所以总的时间复杂度是：O(KN*logN)​，空间复杂度是O(KN)。

四、终极动态规划

以dp[k][m]表示k个鸡蛋扔m次最多可以确定的多少层的楼，那么第一个大于等于n的下标m就是扔鸡蛋的次数了。到第i层的时候，依旧是有两种策略：

1. 鸡蛋碎了，此时鸡蛋减1，扔的次数减1，接下来可以检测出来的楼层是dp[k-1][m-1]。
2. 鸡蛋没碎，扔的次数减1，接下来可以检测出来的楼层是dp[k][m-1]。

所以第i个鸡蛋能确定的楼层的总数是：dp[k-1][m-1] + dp[k][m-1] + 1，即鸡蛋碎了的时候能确定的楼层数加上鸡蛋没碎的时候能确定的楼层数再加上本层。

代码：

// k是鸡蛋个数，n是楼层，两个都大于等于1
int superEggDrop(int k, int n) {
    int i, j;
    vector<vector<int>> v(k + 1, vector<int>(n + 1, 0));

    for (j = 1; v[k][j - 1] < n; j++) { // 扔鸡蛋的次数
        for (i = 1; i <= k && v[k][j - 1] < n; i++) { // 鸡蛋个数
            v[i][j] = v[i - 1][j - 1] + v[i][j - 1] + 1;
        }
    }
    return j - 1;
}

要注意的地方是循环条件终止条件是v[k][j-1] >= n，为什么是j-1呢，因为第一层for循环的j表示的是第j次扔鸡蛋能确定的层数，此时层数还没有确定，还要在下面的循环中计算得到。如果使用v[k][j]会出现死循环导致数据溢出。

时间复杂度O(K*N)，提交后执行用时大大减少：

继续优化

上面已经计算出来状态转移方程是：

$$dp[k][i]=dp[k-1][i-1] + dp[k][i-1] + 1$$

可以看到，当前状态实际上只与前面一列的状态有关，可以只保存前面一列状态的数据，空间复杂度为O(K)。

int superEggDrop(int k, int n) {
    int i, j;
    vector<vector<int>> v(k + 1, vector<int>(2, 0));
    // 第0列作为前一列的备份列，第1列作为当前列
    for (j = 1; v[k][0] < n; j++) {
        for (i = 1; i <= k && v[k][j - 1] < n; i++) {
            v[i][1] = v[i - 1][0] + v[i][0] + 1;
        }

        // 拷贝第1列到第0列
        for (i = 0; i <= k; i++) {
            v[i][0] = v[i][1];
        }
    }
    return j - 1;
}

[leetcode]300-最长上升子序列

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/longest-increasing-subsequence

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例：

• 输入: [10,9,2,5,3,7,101,18]
• 输出: 4
• 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明：

• 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
• 你算法的时间复杂度应该为O(n^2)。

进阶：你能将算法的时间复杂度降低到O(nlogn)吗?

二、题解

首先要搞清楚的是题意：求最长上升子序列。子序列不是子串，两者的区别是子序列可以不连续，子串必须连续。

例如：[1, 3, 5, 2, 9]，最长上升子序列是[1, 3, 5, 9]，最长上升子串是[1, 3, 5]。

2.1 暴力法

题目的一个要求是用O(n^2)的时间复杂度来完成这个问题，如果有O(n^2)的时间复杂度，可以直接使用暴力破解的办法：

// 伪代码
for (i = 0; i < size; i++) {
    for (j = i; j < size; j++) {
        // 存在一个上升序列，和加一
        if (nums[j] >= nums[i])
            val[i][j] +=1;
    }
}

算法的时间复杂度和空间复杂度都是O(n^2)。

2.2 动态规划

以dp[i]表示到第i个元素时的最大上升子序列长度，那么dp[i]就等于数组中上一个小于5的元素的最大上升子序列长度加1。

以[10,9,2,5,3,7]为例，i=5时如何求dp[i]？此时nums[i]=7，要想构造上升序列，它前面的数字都小于7才行。左边小于7的数字有三个：2、5和3。

• 在数字1的地方，最大上升子序列的长度是1。
• 在数字5的地方，最大上升子序列的长度是2；
• 在数字3的地方，最大上升子序列的长度是2。

因为7大于三个数字，所以到达7的时候最大子序列长度肯定要加1，这个时候只有在上面三个数字中最大的上面加才能保证数字7的子序列最大。因此可以归纳出来的状态转移方程为：

$$dp[i]=max(dp[0], dp[1],..., dp[n]), n<i, nums[n]<=nums[i].$$

使用动态规划的时间复杂度也是O(n^2)，空间复杂度O(n)。

2.3 二分法求解

二分法不容易想出来，即使是看题解也是看了几遍才明白。

考虑一个问题：假设存在数组tails，tails[i]表示最大上升子序列长度为i的子序列的末尾元素的最小值，这种情况下tails的长度就是最大子序列的长度了。存不存在这么一个数组呢，有没有办法构造出这样的一个数组？答案是肯定的。

以[10, 9, 2, 5, 7]为例解释tails数组每个元素的意义：

1. 所有的数字都是长度为1的子序列，其中最小的数字是2，所以tails[1]=2。
2. 长度为2的子序列有[2, 5], [2, 7]和[5, 7]，其中末尾数最小的是5，所以tails[2]=5。
3. 长度为3的子序列只有[2, 5, 7]，末尾数只有一个就是7，所以tails[3]=7。

如果我们能构造出这个数组，那么问题就解决了。那么关键的问题是：如何知道遍历到哪个元素的时候，它的子序列长度是多少？

首先，暂且假设这个数组存在。结合tails数组的特性，可以确定的一个问题是tails[i]肯定大于tails[i-1]，tails数组一定严格递增。因为题目求的是上升子序列，而tails数组保存的是每个子序列中的最小值，所以子序列右边的元素肯定大于左边的。

一个要注意的问题是tails[i]表示的是长度为i的子序列的末尾元素的最小值，以[1, 5, 3, 4]为例，最大上升子序列长度为2的有两个：[1, 5]和[1, 3]，如果不取最小的末尾元素3，那么tails数组就是[1, 5]，当遍历到4的时候，找到第一个大于它的数是5，此时下标等于2，也就是说最大上升子序列长度就是2。而实际上应该是3（子序列[1, 3, 4]），结果不对。

结合这个结论，在判断nums[i]的时候，只要从左到右找到第一个大于它的值的时候（使用二分法查找），这个下标就是它的最大子序列长度了。

这种情况下时间复杂度为O(nlogn)​，空间复杂度为O(n)。

三、代码

3.1 动态规划

int lengthOfLIS_DP(vector<int> &nums) {
    int res = 1;
    size_t i, j;
    vector<int> dp(nums.size(), 1);

    if (nums.empty())
        return 0;

    for (i = 0; i < nums.size(); i++) {
        // 遍历所有比当前数字小的元素
        for (j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                // 更新dp数组
                dp[i] = max(dp[i], dp[j] + 1);
                // 更新结果
                res = max(dp[i], res);
            }
        }
    }

    return res;
}

3.2 二分法

通过二分法找到区间内第一个大于目标的元素：

/*
 * 在区间[left, right]找到第一个大于等于目标的元素
 * @v 待查找的数组
 * @left 左边界，包含
 * @right 右边界，包含
 * @return 找到返回元素的下标，否则返回-1
 */
int find_first_ge(vector<int> &v, int left, int right, int target) {
    int mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (v[mid] >= target) {
            if (mid == left || v[mid - 1] < target)
                return mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

求最长上升子序列：

int lengthOfLIS_BINSEARCH(vector<int> &nums) {
    vector<int> tails(nums.size(), 0);
    int i, idx, max_len;

    if (nums.empty())
        return 0;

    max_len = 0;
    for (i = 0; i < nums.size(); i++) {
        idx = find_first_ge(tails, 0, max_len - 1, nums[i]);
        if (idx < 0) {
            // 没有找到一个比当前元素小的，扩充
            tails[max_len++] = nums[i];
        } else {
            // 找到了，替换掉
            tails[idx] = nums[i];
        }
    }
    return max_len;
}

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/house-robber

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1：

• 输入: [1,2,3,1]
• 输出: 4
• 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

• 输入: [2,7,9,3,1]
• 输出: 12
• 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

二、题解

假设当前是第n家房屋，已经偷到了x元。当前有两种选择：偷或者不偷。

1. 如果偷了，那么说明前面一家房屋是不能偷的，否则会报警。这个时候偷到的金额为x[n - 2] + nums[n]。
2. 如果不偷，说明前面一家房屋肯定是要偷的，不然少偷了一家。这个时候偷到的金额为x[n - 1]。

两种情况，如何选择？肯定是选择两者中金额更大的，那么就能得到状态转移方程为：

$$dp[i]=max(dp[i - 1], dp[i - 2] + nums[i])$$

因为当前状态只于前面两个状态有关，因此没必要分配dp数组，使用固定的变量来表示就行了（和斐波那契数列一样）。状态转移方程可修改为：

$$amount = max(prev, pprev + nums[n])$$

其中prev是上一个状态的最大值，pprev是上上个状态的最大值，nums[n]是当前第n个房屋的金额。

三、代码

int rob(vector<int> &nums) {
    int max_amount = 0, pprev, prev;
    size_t i;

    if (nums.size() < 1)
        return 0;

    pprev = 0;
    prev = nums[0];
    max_amount = prev;
    for (i = 1; i < nums.size(); i++) {
        max_amount = max(prev, pprev + nums[i]);
        pprev = prev, prev = max_amount;
    }
    return max_amount;
}

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/coin-change

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1：

• 输入：coins = [1, 2, 5], amount = 11
• 输出：3
• 解释：11 = 5 + 5 + 1

示例 2：

• 输入：coins = [2], amount = 3
• 输出：-1

说明:

你可以认为每种硬币的数量是无限的。

二、题解

以示例一种的[1, 2, 5]三种硬币为例，当要凑到11块钱的时候，什么时候硬币个数最小？

只有在凑到11之前的硬币最少，凑够11的硬币才最少。凑到11块一种有三种可能性：

1. 已经有10块了，再凑1块得到11块。
2. 已经有9块了，再凑2块得到11块。
3. 已经有6块了，再凑5块得到11块。

也就是说，手里面当前已经揣了10块、9块或是6块钱，这个时候哪个的硬币数量最少，凑成的11块钱硬币才最少。很明显又是一个动态规划，以dp[i]表示amount=i时候的最优解个数，那么dp[i]的状态转移方程为：

$$\begin{equation} dp(i)= \begin{cases} -1 & amount < 0\\ 0 & amount = 0 \\ min(dp[i-coin1], dp[i-coin2], ...) + 1 & amount > 0\end{cases} \end{equation}$$

三、代码

class Solution {
public:
    int coinChange(vector<int> &coins, int amount) {
        int i, cnt;
        // 初始化为int类型的最大值以方便做特殊处理
        vector<int> dp(amount + 1, INT_MAX);

        if (amount < 0)
            return -1;

        dp[0] = 0;
        for (i = 1; i <= amount; i++) {
            for (auto coin: coins) {
                // dp[i - coin]存在并且有最小值才行
                if (i - coin < 0 || dp[i - coin] == INT_MAX)
                    continue;
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/wildcard-matching

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

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

• '?' 可以匹配任何单个字符。
• '*' 可以匹配任意字符串（包括空字符串）。

两个字符串完全匹配才算匹配成功。

说明：

• s 可能为空，且只包含从 a-z 的小写字母。
• p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

示例 1：

• 输入：s = "aa", p = "a"
• 输出：false
• 解释："a" 无法匹配 "aa" 整个字符串。

示例 2：

• 输入：s = "aa", p = "*"
• 输出: true
• 解释: '*' 可以匹配任意字符串。

示例 3：

• 输入：s = "cb", p = "?a"
• 输出：false
• 解释：'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

二、题解

动态规划，使用dp[i][j]表示字符串s的第i个字符和模式串p的第j个字符的匹配状况，如果匹配上了设置为true，否则为false。

dp[i][j]何时为true：

• 当s[i] == p[j]或者p[j] == '?'的时候，只要两个字符串前面的字符匹配上（也就是dp[i - 1][j - 1] = ture），那么这里的两个字符也匹配上。

• 当s[i] == '*'的时候，有两种情况能匹配上：

  1. 字符串s的前面一个字符就已经能匹配上模式串p了，即dp[i - 1][j] = true时，如s=ab, p=ab*。
  2. 模式串p的前面一个字符已经匹配上字符串s了，即dp[i][j - 1] = true时，如s=abcd, p=ab*。
  3. 注意这里的状态并不是d[i - 1][j - 1]控制的，因为一个*可以匹配多个字符，而?只能匹配一个字符。

初始情况下：

• dp[0][0] = true：空字符串s和空字符p，匹配上。
• dp[0][j]：s为空，p不为空，只有p是*时值才为true。
• dp[i][0]：s不为空，p为空，永远不可能匹配上，都是false。

基于以上几点，就可以写出代码了。

三、代码

bool isMatch(string s, string p) {
    int i, j;
    vector<vector<bool>> dp(s.length() + 1, vector<bool>(p.length() + 1, false));

    // 初始化数组
    dp[0][0] = true;
    for (j = 1; j <= p.length(); j++) {
        if (p[j - 1] == '*')
            dp[0][j] = dp[0][j - 1];
        else
            break;
    }

    for (i = 1; i <= s.length(); i++) {
        for (j = 1; j <= p.length(); j++) {
            if ((s[i - 1] == p[j - 1] || p[j - 1] == '?'))
                dp[i][j] = dp[i - 1][j - 1];
            if (p[j - 1] == '*' && (dp[i - 1][j] || dp[i][j - 1])) {
                dp[i][j] = true;
            }
        }
    }
    return dp[s.length()][p.length()];
}