动态规划题目

Posted on | Post modified: | In |
Words count in article: 7.7k

线性DP

最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int longestCommonSubsequence(string text1, string text2) {
    int m = size(text1), n = size(text2);
    int dp[m+1][n+1];
    memset(dp, 0, sizeof dp);
   
    for (int i = 1; i <= m; ++ i) {
        for (int j = 1; j <= n; ++ j){
            if (text1[i-1] == text2[j-1]) 
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] =  max(dp[i][j-1], dp[i-1][j]);
        }
    }
    return dp[m][n];
}

三角形最小路径和

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

例如，给定三角形：

1
2
3
4
5
6
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

  • DP

对每个位置，它的最短路径可以通过上一层与它相邻的两个节点的最短路径加上它自身的长度得到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int minimumTotal(vector<vector<int>>& triangle) {
    int m = size(triangle);
    if (!m) return 0;
    int dp[m+1], _min = 1e9;
    memset(dp, 0x7f, sizeof dp);
    dp[0] = triangle[0][0];
    for(int i = 1; i < m; ++ i) 
        for (int j = i; j >= 0 ; -- j){
            if (j == 0) dp[j] = dp[j] + triangle[i][j];
            //else if (j == i) dp[j] = dp[j-1] + triangle[i][j];
            else dp[j] = min(dp[j], dp[j - 1]) + triangle[i][j];
        }

    for (int i = 0; i < m; ++ i) 
        if (_min > dp[i]) _min = dp[i];
    return _min;
}

最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

1
2
3
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

因为要求的是连续的，因此每次求最大和的时候，只需要与左边位置的最大和相加即可。那么只要左边的最大和是小于0的，就不用于左边部分保持连续了。每次只计算左边一个位置，因此只需要一个变量来保存当前位置左边的最大和。

1
2
3
4
5
6
7
8
9
10
int maxSubArray(vector<int>& nums) {
    int n = size(nums);
    if (!n) return 0;
    int f = 0, _max = -INT_MAX;
    for (const auto & i : nums) {
        f = max(f + i, i);
        _max = max(_max, f);
    }
    return _max;
}

最长公共子序列

1
2
3
4
5
6
7
for (int i = 1; i <= m; ++ i) {
    for (int j = 1; j <= n; ++ j) {
        f[i][j] = max(f[i - 1][j], f[i][j - 1]);
        if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
    }
}
cout << f[m][n];

最长上升子序列

  • 普通DP
1
2
3
4
5
6
7
8
9
10
11
for (int i = 1; i <= n; i ++ ) cin >> a[i];
    
    for (int i = 1; i <= n; i ++ ){
        f[i] = 1;
        for (int j = 1; j < i; j ++ )
            if(a[i] > a[j])                     // 遍历i之前小于a(i)的f(j)，若f(j)+1大于f(i)，则更新
                f[i] = max(f[i], f[j] + 1);
    }
    
    int res = 0; 
    for (int i = 1; i <= n; i ++ ) res = max(res, f[i]);
  • 贪心 + 二分

，维护每个子序列的【结尾】的最小数值，这样后面的数如果小于它则新的子序列长度不会超过它，如果大于它则长度一定大于它，因此这个序列具有单调性。则可以通过二分来更新这个序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int lengthOfLIS(vector<int>& nums) {
    int n = size(nums);
    int f[n+1];
    memset(f, 0, sizeof f);
    f[0] = -1e9; 
    int len = 0;
    for (int i = 0; i < n; ++ i) {
        // 遍历整个序列
        int l = 0, r = len;
        while (l < r) {
            int mid = l + r + 1>> 1;
            // 在f中找比当前数小的最大的数
            if (f[mid] < nums[i]) l = mid ;
            else r = mid - 1;
        }
        f[l + 1] = nums[i];// 该数的后面即当前数的插入位置
        len = max(len, l + 1);  // 保存最远位置
    }
    return len;
}

鸡蛋掉落

  • 动态规划

首先明确当只有一个鸡蛋时只能挨个挨个试，而鸡蛋充足时最快的方式是直接二分查找。现在可能出现的情况是鸡蛋不足，如何利用有限的步数保证能遍历所有情况。具体的任务就是如何确定每一步鸡蛋扔的楼层。鸡蛋扔出去无非两种情况，碎或者不碎。碎了的话就往下找，此时楼层为扔时楼层的下面部分，鸡蛋损失1个。不碎的话楼层为扔时楼层的上面部分，鸡蛋无损失。然后去这两个子问题中继续求解，因为最终步数由两个子问题中较大的决定，同时目标是最小化步数，于是得到状态转移方程：

这是一个关于楼层数和鸡蛋数的二维DP，并且求解一个状态转移的时候需要枚举当前可能的所有楼层，找到使得两问题中最大问题最小的楼层。因此直接计算的话复杂度是$O(N^2K)$ ，下面的代码会超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int superEggDrop(int K, int N) {
    if (N < 2) return N;
    int f[N+1][K+1];
    memset(f, 0, sizeof f);
    for (int i = 0; i <= N; ++ i) f[i][1] = i;   //初始化，只有一个鸡蛋时只能逐层往上试

    for (int i = 1; i <= N; ++ i) {
        for (int k = 2; k <= K; ++ k) {
            f[i][k] = INT_MAX;
            for (int j = 1; j <= i; ++ j) {
                f[i][k] = min(f[i][k], max(f[j - 1][k - 1], f[i - j][k]) + 1);
            }
        }
    }
    return f[N][K];
}
  • 动态规划+二分

再观察这两个子问题，发现它们随着选定的楼层一个单增一个单减，是一个此消彼长的变化。于是它们的最大值的最小点会在交点处取得，根据这个性质可以用二分来快速找到这个点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int superEggDrop(int K, int N) {
    if (N < 2) return N;
    int f[N+1][K+1];
    memset(f, 0, sizeof f);
    for (int i = 0; i <= N; ++ i) f[i][1] = i;

    for (int i = 1; i <= N; ++ i) {
        for (int k = 2; k <= K; ++ k) {
            f[i][k] = INT_MAX;
            // for (int j = 1; j <= i; ++ j) {
            //     f[i][k] = min(f[i][k], max(f[j - 1][k - 1], f[i - j][k]) + 1);
            // }
            int l = 1, r = i;
            while (l < r) {
                int mid = l + r >> 1;
                if (f[mid - 1][k - 1] >= f[i - mid][k]) r = mid;
                else l = mid + 1;
            }
            f[i][k] = min (f[i][k], max(f[l - 1][k - 1], f[i - l][k]) + 1);
        }
    }
    return f[N][K];
}
  • 动规（逆向）

上面的思路是给定楼层和鸡蛋，然后在楼层区间搜索一个使得分割后的楼层的遍历步数总体最小的楼层位置，这样每次状态更新都需要在所有楼层中查找。如果不管需要验证的楼层有多少，也不管鸡蛋有多少，直接在当前层扔出鸡蛋，也会两个结果，鸡蛋碎或不碎。重新定义转移状态为$f(i, k)$表示在有$k$个鸡蛋的情况下，使用$i$ 步能确定的最大楼层。如果鸡蛋碎了，那么当前能够确认的层数是当前层 + 上一步用$k-1$个鸡蛋能确认的楼层数，即：$1 + f(i - 1, k - 1)$ ，同时还有鸡蛋未碎的情况，因此还得加上上一步用$k$个鸡蛋能确认的楼层数：$f(i-1, k)$ 。于是得到了关于步数和楼层的状态转移方程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int superEggDrop(int K, int N) {
    if (N == 1) return 1;
    int f[N + 1][K + 1];
    memset(f, 0, sizeof f);

    for (int i = 1; i <= K; ++ i) f[1][i] = 1;  // 

    for (int i = 2; i <= N; ++ i) {      // 枚举可能的步数（最多N步）
        for (int j = 1; j <= K; ++ j) {  // 每步可能拥有的鸡蛋数（都没碎时拥有最多的数量）
            f[i][j] = 1 + f[i - 1][j] + f[i - 1][j - 1]; // 上一步 + 鸡蛋碎/没碎
        }
        if (f[i][K] >= N) return i;
    }
    return -1;
}
  • 优化一维
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int superEggDrop(int K, int N) {
    if (N == 1) return 1;
    int f[K + 1];
    memset(f, 0, sizeof f);

    for (int i = 1; i <= K; ++ i) f[i] = 1;

    for (int i = 2; i <= N; ++ i) {
        for (int j = K; j >= 1; -- j) {
            f[j] = 1 + f[j] + f[j - 1];  // 使用上一层(i - 1)的状态
        }
        if (f[K] >= N) return i;
    }
    return -1;
}

俄罗斯套娃信封

这个问题就是将最长上升子序列从一维扩展到了二维，可对其中一维进行排序后使用LIS，但这里不允许相同的长度套娃，因此在排序时，需要将重复的数的另一维逆序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int maxEnvelopes(vector<vector<int>>& ev) {
    int n = size(ev); if (!n) return 0;
    auto comp = [] (vector<int> &a, vector<int> &b) {
        return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];  // 小于为升序，大于为逆序
    };
    sort(ev.begin(), ev.end(), comp);
    
    // LIS 最长上升子序列
    int f[n + 1], max_len = 0;
    memset(f, 0, sizeof f);
    for (const auto &c : ev) {
        int l = 0, r = max_len;
        while (l < r) {            // 查找小于当前数的最大值（左半区间右端）
            int mid = l + r + 1>> 1;
            if (f[mid] < c[1]) l = mid;
            else r = mid - 1;
        }
        //auto l = lower_bound(f, f + max_len, c[1]) - f;
        f[l+1] = c[1];
        max_len = max(max_len, int(l+1));
    }
    
    return max_len;
}

打家劫舍

不能偷相邻的，按理说相邻涉及到左相邻和右相邻，但是在最右端是没有右邻居的。考虑将每段序列看作一个子问题，那么只需计算最右端的最大盗窃数量即可，状态转移方程为

每个状态只与之前的两个状态相关，因此可用两个变量来保存，将一维DP优化到$O(1)$空间。

1
2
3
4
5
6
7
8
9
10
11
int rob(vector<int>& a) {
    int n = size(a);
    // 每次更新只需要前两个变量和序列a
    int tmp, last = 0, now = 0;
    for (int i = 0; i < n; ++ i) {
        tmp = now; // 保存当前，作为下次迭代的last
        now = max(last + a[i], now);
        last = tmp;
    }
    return now;
}

打家劫舍 2

2在之前1的条件下将左端与右端连了起来，这样便不能再用端点的特殊情况，即任何点都需要判断左邻居和右邻居。但是对于左端点和右端点，发现它俩只能同时取一个，那么可按端点分两种情况出来($[0,\;n-1],\;[1,\;n]$)，只要去掉了端点，这个问题便退化成了1问。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int rob(vector<int>& nums) {
    int tmp, last = 0, now = 0;
    int res, n = size(nums);
    if (n == 1) return nums[0];  // 因为会去掉一个点，特判一下
    auto fun = [&] (int l, int r) {
        last = 0, now = 0;
        for (int i = l; i < r; ++ i) {
            tmp = now;
            now = max(now, last + nums[i]);
            last = tmp;
        }
        return now;
    };
    res = max(fun(0, n - 1), fun(1, n));
    return res;
}

打家劫舍 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct dp {
    int select;
    int notSel;
};
dp helper(TreeNode* root) {
    if (!root) return dp{0, 0};
    dp left = helper(root->left);
    dp right = helper(root->right);
    // 
    int sel = root->val + left.notSel + right.notSel;   // 选择当前根，则子节点不能选
    int nse = max(left.select, left.notSel) + max(right.select, right.notSel); // 不选当前根，子节点不一定会选，选最大的情况
    return dp{sel, nse};
}

int rob(TreeNode* root) {
    auto res = helper(root);
    return max(res.select, res.notSel);
}

股票系列

买卖股票的最佳时机

只能交易一次

此时遍历时维护之前最小的即可。

1
2
3
4
5
6
7
8
9
10
11
int maxProfit(vector<int>& prices) {
    int res = 0;

    int min_ = INT_MAX;
    for (int x : prices) {
        res = max(res, x - min_);
        min_ = min(min_, x);
    }

    return res;
}

买卖股票的最佳时机 2

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次交易）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

这个题有较多做法，因为可以买入/卖出无限多次，那么只要是收益为正的交易都可以计算。

  1. 遍历序列，相邻股价之差只要是正的便加上。
  2. 搜索所有的波谷波峰，将它们的差值加上。
  3. 动态规划

对于动态规划，除了第i天的股价外，还需要确定当天是持有股票还是未持有，这样才能判断是买入还是卖出。设$dp(i, 0),\;dp(i, 1)$分别表示第$i$天未持股和持股，则可以写出它们的转移方程为：

1
2
3
4
5
6
7
8
// 初始化
dp[0][0] = 0, dp[0][1] = - prices[0];
for (int i = 1; i < n; ++ i) {
    dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
    dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}

return dp[n - 1][0];

其中第二维实际只有两个变量，并且枚举的过程中只用到了相邻前一天的结果，因此可用两个变量来代替二维数组。

1
2
3
4
5
6
7
int stock = - prices[0], cash = 0;
for (int i = 1; i < n; ++ i) {
    // 如果cash更新为stock + prices[i] ，带入二式，它并不会影响下一个式子更新
    cash = max(cash, stock + prices[i]);
    stock = max(stock, cash - prices[i]);
}
return cash;

按理说更新第一个式子前应该将它之前的数值保存的，因为下个式子的更新会用到。但是观察它更新后的结果，即使cash更新产生了变化，将变化带入二式它不会影响最终结果。

买卖股票的最佳时机 3

与上一题想比，这题限制最多只能交易两次。这就需要求出最高和次高收益 的交易，这样之前两个类似贪心的方法就不能用了。

本题增加了一个限制：交易次数。直接用之前的思路可以添加一维状态，用来表示第几次交易：比如$dp(i, k, 0)$表示第i天时处于第K 次交易的未持有状态（即还未买入），1表示第k次交易已持股状态。则对于某一天的第k次交易，其状态转移与上一题是一样的：

即当前未持股可以从之前就未持股或之前持股但是卖出 而转移过来，当前持股可以从之前就持股或之前未持股但是买入而转移过来。这里因为k比较小，只有2，所以可以不用循环，直接展开。后面的问题当k大于2时其实就是同样的方法扩展而已。

初始化： 这里需要将第一天进行第几次买入都初始化为 - prices[0]，不然在计算时会取到没花钱的0作为买入状态。

int maxProfit(vector<int>& prices) {
    int n = size(prices);
    if (n < 2) return 0;
    int dp[n][3][2];
    memset(dp, 0, sizeof dp);
    dp[0][0][1] = - prices[0]; // 
    dp[0][1][1] = - prices[0];
    for (int i = 1; i < n; ++ i) {
        dp[i][0][1] = max(dp[i-1][0][1], dp[i-1][0][0] - prices[i]); // 第一次买入
        dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][0][1] + prices[i]); // 第一次出售
        dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][1][0] - prices[i]); // 第二次买入
        dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][1][1] + prices[i]); // 第二次出售
    }
    return dp[n-1][2][0];
}

​

显然这个DP同之前一样可以优化，每个状态都只用到前一天的，因此不需要保存所有天数的状态。这里k为2，买入卖出占2个状态，实际也只需要4个变量就能表示，但是用一个3x2数组也无所谓。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int maxProfit(vector<int>& prices) {
    int n = size(prices);
    if (n < 2) return 0;
    int dp[3][2];
    memset(dp, 0, sizeof dp);
    dp[0][1] = - prices[0];// 
    dp[1][1] = - prices[0];
    for (int i = 1; i < n; ++ i) {
        dp[0][1] = max(dp[0][1], dp[0][0] - prices[i]); 
        dp[1][0] = max(dp[1][0], dp[0][1] + prices[i]); // 
        dp[1][1] = max(dp[1][1], dp[1][0] - prices[i]); // 
        dp[2][0] = max(dp[2][0], dp[1][1] + prices[i]); // 
    }
    return dp[2][0];
}

这题还有个特殊的方法，因为k=2，所以这题相当于求最高和次高的收益。他俩一定是不重合的，因此可以通过顺序扫描和逆序扫描两次遍历来找出两个较高收益。因为不重合，所以用扫描经过的点将前段最高收益和后段最高收益区分开。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int maxProfit(vector<int>& prices) {
    int n = prices.size();
    int f[n + 1], res = 0;
    memset(f, 0, sizeof f);

    // 从左往右，记录当前位置之前进行的交易能得的最大利润
    for (int i = 1, minv = INT_MAX; i <= n; ++ i) {
        f[i] = max(f[i - 1], prices[i - 1] - minv);  // 0 ~ i - 1段的最大收益
        minv = min(minv, prices[i - 1]);   // minv表示之前股价的最小点
    }

    // 从右往左，计算从当前位置到结束位置进行的交易能得的最大利润
    int max_profit = 0, maxv = 0;
    for (int i = n ; i ; -- i) {
        max_profit = (max_profit, maxv - prices[i - 1]);
        maxv = max(maxv, prices[i - 1]);
        res = max(res, f[i - 1] + max_profit );  // 前面段的最大收益和 
    }
    return res;
}

买卖股票的最佳时机 4

与之前类似，将变化的k纳入循环之中即可，由于k可能很大，这时问题实际已退化到可以交易任意次的情况，因此在前面加入判别即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int maxProfit(int k, vector<int>& prices) {
    int n = size(prices);
    if (n < 2) return 0;
    
    // 当k较大时，问题退化为可以交易任意次
    if (k > (n >> 1)) {
        int sell = 0, buy = -prices[0];
        for (int i = 1; i < n; ++ i) {
            sell = max(sell, buy + prices[i]);
            buy = max(buy, sell - prices[i]);
        }
        return sell;
    }
    int dp[k+1][2];
    memset(dp, 0, sizeof dp);
    
    for (int i = 0; i < k; ++ i) dp[i][1] = - prices[0];   // 初始化第一天第k次买入

    for (int i = 1; i < n; ++ i) {
        for (int j = 1; j <= k; ++ j){
            dp[j][0]   = max(dp[j][0],   dp[j-1][1] + prices[i]);  // 未持 <= 之前未持股 或 上次交易持股并卖出
            dp[j-1][1] = max(dp[j-1][1], dp[j-1][0] - prices[i]);  // 持股 <= 之前已持股 或 上次交易未持并买入
        }
    }     
    return dp[k][0];
}

买卖股票含冷冻期

距离上次交易需要有一天冷冻期，即卖出后不能立马买。相当于依赖的状态需要用到前两天，只需稍微改动即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int maxProfit(vector<int>& prices) {
    int n = prices.size();
    if (n < 2) return 0;

    int dp[n + 1][2];
    memset(dp, 0, sizeof dp);
    dp[0][1] = dp[1][1] = - prices[0];

    for (int i = 2; i <= n; ++ i) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]);
        dp[i][1] = max(dp[i - 1][1], dp[i - 2][0] - prices[i - 1]);            
    }
    return dp[n][0];
}

买卖股票含手续费

1
2
3
4
5
6
7
8
9
10
11
int maxProfit(vector<int>& prices, int fee) {
    int n = prices.size();
    if (n < 2) return 0;
    
    int buy = - prices[0], sell = 0;   // 状态： 持有、未持有
    for (int i = 1; i < n; ++ i) {
        buy = max(buy, sell - prices[i]);
        sell = max(sell, buy + prices[i] - fee);  // 卖出时完成这笔交易，支付手续费
    }
    return sell;
}

秋叶收藏集

小扣出去秋游，途中收集了一些红叶和黄叶，他利用这些叶子初步整理了一份秋叶收藏集 leaves， 字符串 leaves 仅包含小写字符 r 和 y， 其中字符 r 表示一片红叶，字符 y 表示一片黄叶。
出于美观整齐的考虑，小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等，但均需大于等于 1。每次调整操作，小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。

输入：leaves = “rrryyyrryyyrr”
输出：2
解释：调整两次，将中间的两片红叶替换成黄叶，得到 “rrryyyyyyyyrr”

题意就是需要将序列分为三个区间，使得所有区间不合条件的叶子最少，比如左区间需要黄叶最少，中区间需要红叶最少，且需要它们总体最少。

字符串匹配

编辑距离

  • 关键点

有三种操作，那么两个字符串在求解到子问题 i， j位置时，它们的上一个状态可以从三种情况转移过来，同时如果当前字符相等的话，就可以节省一次操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int minDistance(string a, string b) {
    int m = size(a), n = size(b);
    int dp[m + 1][n + 1];
    memset(dp, 0, sizeof dp);
    for (int i = 0; i <= n; ++ i) dp[0][i] = i;
    for (int i = 0; i <= m; ++ i) dp[i][0] = i;

    for (int i = 1; i <= m; ++ i) {
        for (int j = 1; j <= n; ++ j) {
            // 初始为之前的三种状态 + 1
            dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
            // 如果相等的话可以少一次操作
            if (a[i - 1] == b[j - 1]) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]); 
        }
    }
    return dp[m][n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int minDistance(string a, string b) {
    int m = size(a), n = size(b);

    int f[n+1];

    for(int i = 0; i <= n; ++ i) f[i] = i; // 

    for (int i = 1; i <= m; ++ i) {
        int pre = i - 1; // 保存上一层的的状态f[i - 1][j - 1],每进入下一层循环j变为0，实际上=f[i-1][0]
        f[0] = i;        // 等价于最开始的初始化f[i][0] = i
        for (int j = 1; j <= n; ++ j) {
            int tmp = f[j];// 刚进入得到的状态是上一层的，保存还未更改的状态
            if (a[i-1] == b[j-1]) f[j] = pre;
            else f[j] = min(f[j], min(f[j-1], pre)) + 1;
            pre = tmp;     // 
        }
    }
    return f[n];
}

通配符匹配

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

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

​ 问号可以匹配单个字符，那么直接将其看作一个万能字符即可，而星号可匹配任意字符串，包括空串，也就是星号可以匹配0次，1次和多次。先设出状态，令$f(i, j)$表示字符串$s$的$i$之前的子串和字符串$p$的$j$之前的子串是否匹配。那么遇到星号的状态转移为：

分别是表示匹配0次，1次和多次的情况，然而匹配1次和多次的情况是可以合并的，都用多次来表示，这样状态表示为：

这个转移方程也可以解释为是否使用星号。

初始化：

​ 当字符串都为空时是匹配的，因此f(0, 0) 应该是匹配的，并且当s为空，p全为*时也是匹配的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
bool isMatch(string s, string p) {
    // s = ' ' + s;
    // p = ' ' + p;
    int m = s.size(), n = p.size();

    bool f[m + 1][n + 1];
    memset(f, 0, sizeof f);
    f[0][0] = true;

    for (int i = 1; i <= n; ++ i) {   // 对应p串开始全是*的情况
        if (p[i - 1] == '*') f[0][i] = true;
        else break;
    }

    for (int i = 1; i <= m; ++ i) {
        for (int j = 1; j <= n; ++ j) {
            if (p[j - 1] == '*'){  // 可以匹配一个/ 匹配多个 / 匹配0个
                f[i][j] |=  f[i - 1][j] | f[i][j - 1];
            }
            else if (p[j - 1] == '?' || p[j - 1] == s[i - 1]){
                f[i][j] = f[i - 1][j - 1];  // 只能匹配当前一个字符
            }
        }
    }
    return f[m][n];
}

正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

  • 动态规划思路

  先从爆搜的思路看这个问题，对于字符串p，因为*的存在，它是可变长的。如果在搜索过程中贪心的让它匹配当前能匹配的最长串，就可能错过回溯能正确匹配的串。比如：

1
2
aaa
a*a

那么对于当前长度的s，可能p有多个能与它匹配的方案，为了在枚举这些方案的时候减少重复计算，就可以使用动态规划的思想，保存之前能够成功匹配的方案。

状态定义： $dp(i, j)$ 表示$s$的$[0, \;i]$范围子串和$p$的$[0, \; j]$范围子串是否能够匹配。

在已知$dp(i - 1, j - 1)$和$s[i], p[j]$的情况，可以根据$s[i] == p[j]$得到$dp(i, j) = dp(i-1,j-1)$。

.表示任意单个字符，因此它可以纳入普通的比较单个字符是否相等的情况。

*则可以复制任意次其前面的字符，其中对应关系为：

0次：$dp(i, j - 2)$

1次：$dp(i-1, j - 2)$

…

n次: $dp(i-n, j -2)$

这样罗列情况太多了，当复制多次(大于等于1)时，可以看作当前*保留，而s串删除末尾一个，这样它将是相同情况，后面再访问到还可以执行同样的操作。得到

$dp(i - 1, j)$

整理得到转移方程：

  • 代码细节
  1. 当两个串都是空串时应该是匹配的，并且当s是空串，p是形如”a*”这样的串应该也是匹配的，它需要初始化$dp(0, 0) = true$。那么$dp(0, 0)$便不能用来表示第一个字符是否匹配，为了方便，在s和p前添加一个空格来适配这种情况。这样如果是空串的话，添加空格后，$dp(1, 1)$表示空串的状 态·。
  2. 还须注意的是字符串下标从$0$开始，因此在判断$dp(i, j)$时，它们实际对应的字符是$s[i-1]$和$p[j - 1]$.
  3. 在$p[j] = ‘*’$的情况下，复制一次和复制多次的情况是可以合并的，可统一表示为$dp(i-1, j)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
bool isMatch(string s, string p) {
    s = ' ' + s;
    p = ' ' + p;
    int m = s.size(), n = p.size();

    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));

    auto match = [&](int i, int j) {
        if (p[j] == '.') return true;
        return s[i] == p[j];
    };

    dp[0][0] = 1;

    for (int i = 1; i <= m; ++ i) {
        for (int j = 1; j <= n; ++ j) {
            if (p[j - 1] == '*') {   
                if (match(i - 1, j - 2)) {  // 遇到*时，去跟它前面的数匹配
                    dp[i][j] = dp[i - 1][j] | dp[i][j - 2]; // 状态转移： * 可用于继续匹配i - 1， 或者*为0次，此时将j-1消去，按i 与 j-2是否匹配转移
                    // 例如 s = aa , p = b*aa  该式结果为匹配 
                }else {
                    dp[i][j] = dp[i][j - 2];   // i和j-1不匹配，只能去匹配j-2了 
                }
            }else {
                if (match(i - 1, j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
            //cout << dp[i][j] << ' ';
        }
    }
    return dp[m][n];
}

区间DP

最长回文子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
string longestPalindrome(string s) {
    int n = s.size(), max_len = 1, start = 0;
    if(n <= 1) return s;

    bool f[n+5][n+5]; 
    memset(f, 0, sizeof f);

    for (int i = 0; i < n; ++ i) f[i][i] = true;

    // 枚举所有区间，只需要判断是否是回文串即可
    int cnt = 0;
    for (int j = 0; j < n;  ++ j)
        for (int i = 0; i < j; ++ i){
            if(s[i] == s[j]){
                if(j - i < 2) f[i][j] = true;
                else f[i][j] = f[i+1][j-1];
            }
            else
                f[i][j] = false;

            if(f[i][j]){
                if (max_len < j - i + 1){

                    max_len = j - i + 1;
                    start = i;
                }
            }
        }

    return s.substr(start, max_len);

}

最长回文子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int longestPalindromeSubseq(string s) {
    int n = size(s);
    int f[n][n];
    memset(f, 0, sizeof f);

    for (int i = 0; i < n; ++ i) f[i][i] = 1;

    // 由于dp公式中需要dp(i + 1, j) , dp(i, j - 1)。因此枚举时需要保证这两个已经更新过，即区间内的点都更新过
    // 可以从递增的枚举右区间，内层递减的枚举左区间，这样左右边界都是更新过的。
    for (int j = 1; j < n; ++ j) {   // 记忆化搜索，
        for (int i = j - 1; i >= 0; -- i) {
            if (s[i] == s[j]) f[i][j] = f[i + 1][j - 1] + 2;
            else f[i][j] = max(f[i + 1][j], f[i][j - 1]);
        }
    }
    return f[0][n - 1];
}

两端DP

执行乘法运算的最大分数

给你两个长度分别 n 和 m 的整数数组 nums 和 multipliers ，其中 n >= m ，数组下标 从 1 开始 计数。

初始时，你的分数为 0 。你需要执行恰好 m 步操作。在第 i 步操作（从 1 开始 计数）中，需要：

  • 选择数组 nums 开头处或者末尾处 的整数 x 。
  • 你获得 multipliers[i] * x 分，并累加到你的分数中。
  • 将 x 从数组 nums 中移除。

在执行 m 步操作后，返回 最大 分数。

题意就是需要在nums中依次为multipliers中的数找到一个数与它相乘，使得所有乘积的和最大。并且只能在nums的两端寻找，nums中的数只能用一次。

因为用过的数不能再用，所以不能贪心。具体点就是需要在nums中找m次，每次有两种不同的选择。将状态设置为左边取走l个数，右边取走r个数的和。观察选择后的结果，是取走左边或右边的一个数，这个状态可从前一个状态转移过来。并且与上一个状态之前的状态（左右分别是第几次取走的）无关。

因此只需要枚举左右取的数量：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int maximumScore(vector<int>& nums, vector<int>& mp) 
{
	int n = nums.size(), m = mp.size();
    vector< vector<int> > dp(m + 1, vector<int>(m + 1, -1e9));
    dp[0][0] = 0; // 左右都未取时为0
    
    for (int l = 0; l < m; ++ l) {
        for (int r = 0; r + l < m; ++ r) {
            dp[l + 1][r] = max(dp[l + 1][r], dp[l][r] + mp[l + r] * nums[l]);
            dp[l][r + 1] = max(dp[l][r + 1], dp[l][r] + mp[l + r] * nums[n - 1 - r]);
        }
    }
    
    int res = -1e9;
    for (int i = 0; i <= m; ++ i) {
        res = max(res, dp[i][m - i]);
    }
    
    return res;
}