动态规划专题

  LeetCode1 小时读完 (大约7593个字)

DP 问题的一般思路

  • DP 定义 ——有时 DP 的更新很难严格遵循定义，需要额外变量保存全局最优结果
  • 初始化 ——初始值可以通过一个简单的特例来确定
  • 递推公式 + 边界条件
  • DP 优化 （可选）

Reference

【注】关于“恰好装满”

  • 如果要求恰好装满背包，可以在初始化时将 dp[0] / dp[i][0] 初始化 0，其他初始化为 -INF。这样即可保证最终得到的 dp[N] / dp[N][M] 是一种恰好装满背包的解；
  • 如果不要求恰好装满，则全部初始化为 0 即可。
  • 可以这样理解：初始化的 dp 数组实际上就是在没有任何物品可以放入背包时的合法状态。
    • 如果要求背包恰好装满，那么此时只有容量为 0 的背包可能被价值为 0 的物品“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是 -INF 。
    • 如果背包并非必须被装满，那么任何容量的背包都有一个合法解，即“什么都不装”，这个解的价值为0，所以初始时状态的值也全部为 0 。

01 背包

HDOJ - 2602

问题描述 

1
2
3
4
5
6
7
8
9
10
有 n 个重量个价值分别为 w_i, v_i 的物品。
从这些物品中选出总重量不超过 W 的物品，使其总价值最大。

示例
1                // 用例数
5 10             // 物品数 背包容量 N <= 1000 , V <= 1000
1 2 3 4 5
5 4 3 2 1

14

二维 DP（无优化）

  • 定义：dp[i][j] := 从前 i 个物品中选取总重量不超过 j 的物品时总价值的最大值 > i 从 1 开始计，包括第 i 个物品
  • 初始化 
    1
    dp[0][j] = 0
  • 状态转移 
    1
    2
    3
    4
    5
    dp[i][j] = dp[i-1][j]            if j < w[i] （当前剩余容量不够放下第 i 个物品）
             = max{                  else （取以下两种情况的最大值）
                    dp[i-1][j],             // 不拿第 i 个物品
                    dp[i-1][j-w[i]] + w[j]  // 拿第 i 个物品
                  }
    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
    34
    35
    36
    // HDOJ 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2602
    int solve(int N, int V, vector<int>& v, vector<int>& w) {

        vector<vector<int> > dp(N + 1, vector<int>(V + 1, 0));  // 不要求装满，初始化为 0 即可

        // 核心代码
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= V; j++) {  // 可能存在重量为 0，但有价值的物品
                if (w[i] > j)               // 如果当前物品的重量大于剩余容量
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
            }
        }
        return dp[N][V];
    }

    int main() {
        int T;      // 用例数
        scanf("%d", &T);
        while (T--) {
            int N, V;                   // N: 物品数量；V: 背包容量
            scanf("%d%d", &N, &V);
            vector<int> v(N + 1, 0);    // 保存每个物品的价值
            vector<int> w(N + 1, 0);    // 保存每个物品的重量
            for (int i = 1; i <= N; i++)
                scanf("%d", &v[i]);
            for (int i = 1; i <= N; i++)
                scanf("%d", &w[i]);

            int ans = solve(N, V, v, w);

            printf("%d\n", ans);
        }
        return 0;
    }

二维 DP（滚动数组）

  • 在上述递推式中，dp[i+1] 的计算实际只用到了 dp[i+1] 和 dp[i]；
  • 因此可以结合奇偶，通过两个数组滚动使用来实现重复利用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// HDOJ 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2602
int solve(int N, int V, vector<int>& v, vector<int>& w) {

    //vector<vector<int> > dp(N + 1, vector<int>(V + 1, 0));  // 不要求装满，初始化为 0 即可
    vector<vector<int> > dp(2, vector<int>(V + 1, 0));  // N+1 -> 2

    // 核心代码
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= V; j++) {  // 可能存在重量为 0，但有价值的物品
            if (w[i] > j)               // 如果当前物品的重量大于剩余容量
                dp[i & 1][j] = dp[(i - 1) & 1][j];
            else
                dp[i & 1][j] = max(dp[(i - 1) & 1][j], dp[(i - 1) & 1][j - w[i]] + v[i]);
        }
    }
    return dp[N & 1][V];  // 这里别忘了 N & 1
}

// main 函数略

一维 DP

  • 定义：dp[j] := 重量不超过 j 公斤的最大价值
  • 递推公式 
    1
    dp[j] = max{dp[j], dp[j-w[i]] + v[i]}     若 j > w[i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// HDOJ 地址：http://acm.hdu.edu.cn/showproblem.php?pid=2602
// 一维 DP（滚动数组）
int solve(int N, int V, vector<int>& v, vector<int>& w) {

    vector<int> dp(V + 1, 0);

    // 核心代码
    for (int i = 1; i <= N; i++) {
        for (int j = V; j >= w[i]; j--) {           // 递推方向发生了改变
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }

    return dp[V];
}

// main 函数略

完全背包

NYOJ - 311

问题描述 

1
2
3
4
01 背包中每个物品只有一个，所以只存在选或不选；
完全背包中每个物品可以选取任意件。

注意：本题要求是背包恰好装满背包时，求出最大价值总和是多少。如果不能恰好装满背包，输出 NO

二维 DP（无优化）

  • 直观思路：在 01 背包的基础上在加一层循环
  • 递推关系： 
    1
    2
    dp[0][j] = 0
    dp[i][j] = max{dp[i - 1][j - k * w[i]] + k * v[i] | 0 <= k}
    1
    2
    3
    4
    5
    6
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= V; j++) {  // 可能存在重量为 0 的物品
            for (int k = 0; k * w[i] <= j; k++)
                dp[i][j] = max(dp[i][j], dp[i-1][j - k*w[i]] + k*v[i]);
        }
    }
    • 关于 k 的循环最坏可能从 0 到 V，因此时间复杂度为 O(N*V^2)
  • 注意到： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    dp[i][j] = max{dp[i - 1][j - k*w[i]] + k*v[i] | 0 <= k}
                                                    ------
             = max{dp[i - 1][j], max{dp[i - 1][j - k*w[i]] + k*v[i]} | 1 <= k}
                                                                       ------
             = max{dp[i - 1][j], max{dp[i - 1][(j-w[i]) - k*w[i]] + k*v[i] | 0 <= k} + v[i]}
                                               --------                      ------  ------
                                 ---------------------------------------------------
             = max{dp[i - 1][j], dp[i][j - w[i]] + v[i]}
                                 ---------------
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= V; j++) {
            if (w[i] > j)
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i]);
            //  dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); // 对比 01 背包
            //                               ---------（唯一区别）
        }
    }
  • 完整代码
    • 注意，这里要求的是恰好装满时的情况，所以需要将 dp[i][0] 全部初始化为 0，其他初始化为 -INF > 以下代码因超内存无法通过 NYOJ 311； > > 可以 AC 的代码，请参考 完全背包（一维 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
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      // NYOJ 311 会报超内存，所以无法测试
      #include <cstdio>
      #include <vector>
      #include <algorithm>
      using namespace std;

      const int inf = 0x80000000;

      void solve() {
          int T;
          scanf("%d", &T);
          while (T--) {
              int N, V;       // N 表示物品种类的数目，V 表示背包的总容量
              scanf("%d%d", &N, &V);
              vector<int> w(N + 1), v(N + 1);  // w 表示重量，v 表示价值
              for (int i = 1; i <= N; i++)
                  scanf("%d%d", &w[i], &v[i]);

              vector<vector<int> > dp(N + 1, vector<int>(V + 1, inf));
              for (int i = 0; i <= N; i++)
                  dp[i][0] = 0;

              for (int i = 1; i <= N; i++) {
                  for (int j = 0; j <= V; j++) {
                      if (j < w[i])
                          dp[i][j] = dp[i - 1][j];
                      else
                          dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i]);
                  }
              }

              if (dp[N][V] > 0)
                  printf("%d\n", dp[N][V]);
              else
                  puts("NO");
          }
      }

      int main() {
          solve();
          return 0;
      }

二维 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// NYOJ 311-完全背包: http://nyoj.top/problem/311 （未通过测试，报运行时错误）
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

void solve3() {
    const int MAX_V = 50000 + 10;
    const int inf = 0x3f3f3f3f;

    int T;
    scanf("%d", &T);
    while (T--) {
        int N, V;       // M 表示物品种类的数目，V 表示背包的总容量
        scanf("%d%d", &N, &V);
        //vector<int> w(N + 1), v(N + 1);  // w 表示重量，v 表示价值
        //for (int i = 1; i <= N; i++)
        //    scanf("%d%d", &w[i], &v[i]);

        //vector<vector<int> > dp(2, vector<int>(V + 1, -inf));
        int dp[2][MAX_V];
        for (int i = 0; i < 2; i++) {
            fill(dp[i], dp[i] + MAX_V, -inf);
            dp[i][0] = 0;
        }

        for (int i = 1; i <= N; i++) {
            int w, v;
            scanf("%d%d", &w, &v);
            for (int j = 0; j <= V; j++) {
                if (j < w)
                    dp[i & 1][j] = dp[(i - 1) & 1][j];
                else
                    dp[i & 1][j] = max(dp[(i - 1) & 1][j], dp[i & 1][j - w] + v);
            }
        }

        if (dp[N][V] > 0)
            printf("%d\n", dp[N & 1][V]);
        else
            puts("NO");
    }
}

int main() {
    solve3();
    return 0;
}

一维 DP

  • 核心代码与 01 背包一致，只有第二层循环的递推方向不同
  • 完整代码 
    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
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    // NYOJ 311-完全背包: http://nyoj.top/problem/311
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <algorithm>
    using namespace std;

    const int MAX_V = 50000 + 10;
    const int inf = 0x80000000;

    void solve2() {
        int T;
        scanf("%d", &T);
        while (T--) {
            int N, V;       // M 表示物品种类的数目，V 表示背包的总容量
            scanf("%d%d", &N, &V);
            //vector<int> w(N + 1), v(N + 1);  // w 表示重量，v 表示价值
            //for (int i = 1; i <= N; i++)
            //    scanf("%d%d", &w[i], &v[i]);

            //vector<int> dp(V + 1, inf);   // 注意 NYOJ 的系统开辟稍大的 vector 就会导致超时
            int dp[MAX_V];
            fill(dp, dp + MAX_V, inf);
            dp[0] = 0;

            for (int i = 1; i <= N; i++) {
                int w, v;
                scanf("%d%d", &w, &v);      // 避免开辟新的内存 
                for (int j = w; j <= V; j++) {
                    dp[j] = max(dp[j], dp[j - w] + v);
                }
            }

            if (dp[V] > 0)
                printf("%d\n", dp[V]);
            else
                puts("NO");
        }
    }

    int main() {
        solve2();
        return 0;
    }

多重背包 TODO

硬币问题

硬币找零

LeetCode - 322. 零钱兑换

问题描述 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
给定不同面额的硬币 coins 和一个总金额 amount。
编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

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

示例 2:

    输入: coins = [2], amount = 3
    输出: -1
    
说明:
    你可以认为每种硬币的数量是无限的。

思路 - 定义：dp[i] := 组成总金额 i 时的最少硬币数 - 初始化： 

1
2
dp[i] = 0       若 i=0
      = INF     其他
- 状态转移 
1
2
3
dp[j] = min{ dp[j-coins[i]] + 1 | i=0,..,n-1 }
    
其中 coins[i] 表示硬币的币值，共 n 种硬币

C++ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int coinChange(vector<int>& coins, int n) {
        int INF = n + 1;
        
        vector<int> dp(n+1, INF);
        dp[0] = 0;
        
        for (auto c: coins) {
            for (int i=c; i<=n; i++) {            //  i >= c
                dp[i] = min(dp[i], dp[i-c] + 1);
            }
        }
        
        return dp[n] < INF ? dp[n] : -1;
    }
};

硬币组合

LeetCode - 518. 零钱兑换 II

C++ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int change(int n, vector<int>& coins) {
        int m = coins.size();
        
        vector<int> dp(n+1, 0);
        dp[0] = 1;
        
        for (auto c: coins) {
            for (int i = c; i <= n; i++) {
                dp[i] += dp[i - c];
            }
        }
        
        return dp[n];
    }
};

最长公共子序列（LCS）

最长公共子序列_牛客网 - 求两个序列的最长公共字序列 - 示例：s1: "BDCABA" 与 s2："ABCBDAB" 的一个最长公共字序列为 "BCBA" - 最长公共子序列不唯一，但是它们的长度是一致的 - 子序列不要求连续

思路 - DP 定义 - 记 s[0:i] := s 长度为 i 的**前缀** - 定义 dp[i][j] := s1[0:i] 和 s2[0:j] 最长公共子序列的长度 - DP 初始化 

1
dp[i][j] = 0    当 i=0 或 j=0 时
- DP 更新 - 当 s1[i] == s2[j] 时 
1
dp[i][j] = dp[i-1][j-1] + 1
- 当 s1[i] != s2[j] 时 
1
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- 完整递推公式 
1
2
3
dp[i][j] = 0                              当 i=0 或 j=0 时
         = dp[i-1][j-1] + 1               当 `s1[i-1] == s2[j-1]` 时
         = max(dp[i-1][j], dp[i][j-1])    当 `s1[i-1] != s2[j-1]` 时
- Code - C++ 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class LCS {
public:
    int findLCS(string A, int n, string B, int m) {
        vector<vector<int> > dp(n+1, vector<int>(m+1, 0));
        // 已经初始化为全 0，就不必再手动初始化 DP 了
        
        for (int i=1; i<=n; i++)
            for (int j=1; j<=m; j++)
                if (A[i-1] == B[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[n][m];
    }
};

最长公共子串

最长公共子串_牛客网

题目描述 

1
2
对于两个字符串，请设计一个时间复杂度为`O(m*n)`的算法，求出两串的最长公共子串的长度。
（这里的 m 和 n 为两串的长度）

思路 - 暴力求解

Longest common substring problem - Wikipedia

暴力求解思路：每当找到一对元素相同时就斜向比较 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class LongestSubstring {
public:
    int findLongest(string A, int n, string B, int m) {
        int ret = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int tmp_ret = 0;
                if (A[i] == B[j]) {  // 每当找到一对元素相同
                    tmp_ret += 1;    // 斜向比较
                    int tmp_i = i + 1;
                    int tmp_j = j + 1;
                    while (tmp_i < n && tmp_j < m && A[tmp_i++] == B[tmp_j++])  // 注意边界
                        tmp_ret++;
                }
                ret = max(ret, tmp_ret);  // 记录最大
            }
        }
        
        return ret;
    }
};
- 注意：如果两个串完全相同的话，时间复杂度将退化为 O(N^3)

思路 - DP - DP 定义 - 记 s[0:i] := s 长度为 i 的**前缀** - 定义 dp[i][j] := s1[0:i] 和 s2[0:j] 最长公共子串的长度 - dp[i][j] 只有当 s1[i] == s2[j] 的情况下才是 s1[0:i] 和 s2[0:j] 最长公共子串的长度 - DP 初始化 
1
dp[i][j] = 0    当 i=0 或 j=0 时
- DP 更新 
1
2
dp[i][j] = dp[i-1][j-1] + 1     if s[i] == s[j]
         = ;                    else pass
- Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class LongestSubstring {
public:
    int findLongest(string A, int n, string B, int m) {
        vector<vector<int> > dp(n + 1, vector<int>(m + 1, 0));
        // 已经初始化为全 0，就不必再手动初始化 DP 了

        int ret = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (A[i - 1] == B[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    ret = max(ret, dp[i][j]);         // 相比最长公共子序列，增加了这行
                }
                else
                    ;                                 // 去掉了这行

        return ret;
    }
};
- DP 优化：空间复杂度 O(N) - 好不容易找到的优化为 O(N) 的代码；多数优化直接优化到了 O(1) - 因为内层循环是逆序的，所以有点不好理解，可以画一个矩阵手推 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
class LongestSubstring {
public:
    int findLongest(string A, int n, string B, int m) {
        if (n < m) {
            swap(n, m);
            swap(A, B);
        }

        vector<int> dp(m, 0);
        
        int ret = 0;
        for (int i = 0; i < n; i++) {
            for (int j = m - 1; j >= 0; j--) {
                if (A[i] != B[j]) {
                    dp[j] = 0;
                }
                else {
                    if (i != 0) {
                        dp[j] = dp[j - 1] + 1;
                    }
                    else {
                        dp[j] = 1;
                    }
                }
                ret = max(ret, dp[j]);
            }
        }

        return ret;
    }
};
- DP 优化：空间复杂度 O(1) - 两个字符串的比较总是按一行一行或一列一列来比较，因此至少要保存一行的数据 - 而如果是按照斜向遍历，其实只要保存一个数据即可

斜向遍历的策略很多，下面的代码是从右上角（row=0, col=m-1）开始遍历 

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
class LongestSubstring {
public:
    int findLongest(string A, int n, string B, int m) {
        int ret = 0;

        for (int row = 0, col = m - 1; row < n;) {
            int i = row;
            int j = col;
            int dp = 0;
            while (i < n && j < m) {
                if (A[i++] == B[j++])  // 注意：无论走哪个分支，i 和 j 都会 ++ 一次
                    dp += 1;
                else
                    dp = 0;

                ret = max(ret, dp);
            }

            if (col > 0) 
                col--;
            else 
                row++;
        }

        return ret;
    }
};

上述代码其实就是把下面的两段循环合并了 

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
class LongestSubstring {
public:
    int findLongest(string A, int n, string B, int m) {
        int ret = 0;
        int dp;

        for (int col = m-1; col >= 0; col--) {
            dp = 0;
            for (int i = 0, j = col; i < n && j < m; i++, j++) {
                if (A[i] == B[j])
                    dp += 1;
                else
                    dp = 0;

                ret = max(ret, dp);
            }
        }

        for (int row = 0; row < n; row++) {
            dp = 0;
            for (int i = row, j = 0; i < n && j < m; i++, j++) {
                if (A[i] == B[j])
                    dp += 1;
                else
                    dp = 0;

                ret = max(ret, dp);
            }
        }

        return ret;
    }
};

最长递增子序列（LIS）

最长递增子序列_牛客网

最长上升子序列 - LeetCode > 牛客假设给定的数组中不存在重复元素，LeetCode 可能存在重复元素

问题描述 

1
2
3
4
5
6
7
8
对于一个数字序列，请设计一个复杂度为O(nlogn)的算法，返回该序列的最长上升子序列的长度

测试样例：
  [2,1,4,3,1,5,6],7
返回：
  4
说明：
  [1,3,5,6] 是其中一个最长递增子序列

思路0 - O(N^2) - LIS 可以转化成 LCS (最长公共子序列) 问题 - 用另一个序列保存给定序列的排序结果 - O(NlogN) - 则问题转化为求这两个序列的 LCS 问题 - O(N^2)

思路1 - O(N^2)解法 - DP 定义 - 记 nums[0:i] := 序列 nums 的前 i 个元素构成的子序列 - 定义 dp[i] := nums[0:i] 中 LIS 的长度 - 实际并没有严格按照这个定义，中间使用一个变量记录当前全局最长的 LIS - DP 初始化 
1
dp[:] = 1  // 最长上升子序列的长度最短为 1
- DP 更新 - O(N^2)的解法 
1
2
3
dp[i] = max{dp[j]} + 1,  if nums[i] > nums[j]
      = max{dp[j]},      else
where 0 <= j < i
如果只看这个递推公式，很可能会写出如下的错误代码

错误代码（点击展开）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 牛客网
class AscentSequence {
public:
    int findLongest(vector<int> nums, int n) {
        vector<int> dp(n, 1);

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++)
                if (nums[i] > nums[j])
                    dp[i] = max(dp[i], dp[j] + 1);
                else
                    dp[i] = max(dp[i], dp[j]);
        }

        return dp[n-1];
    }
};
- 这段代码的问题在于 dp[i] 应该等于 max{dp[j]} 对应的那个 dp[j]+1，且只增加一次 - 这么写可能会导致 dp[i] 被增加多次 > 动态规划求解最长递增子序列的长度 - hapjin - 博客园

  • 下面是网上比较流行的一种递推公式 
    1
    2
    3
    dp[i] = dp[j] + 1,  if nums[i] > nums[j] && dp[i] < dp[j] + 1
          = pass,       else
    where 0 <= j < i
    • 注意：此时并没有严格按照定义处理 dp，它只记录了当 nums[i] > nums[j] && dp[i] < dp[j] + 1 时的 LIS；不满足该条件的情况跳过了；所以需要额外一个变量记录当前已知全局的 LIS
  • Code 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    // 牛客网
    class AscentSequence {
    public:
        int findLongest(vector<int> nums, int n) {
            vector<int> dp(n, 1);

            int ret = 1;
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < i; j++)
                    if (nums[i] > nums[j] && dp[i] < dp[j] + 1)
                        dp[i] = dp[j] + 1;

                ret = max(ret, dp[i]);
            }

            return ret;
        }
    };

思路2 - O(NlogN) - 该解法的思想是：长度为 i 的 LIS 的尾元素应该大于长度为 i-1 的尾元素 - DP 定义 - 定义 dp[i] := 长度为 i 的 LIS 的最小尾元素 - DP 更新 - 二分查找 nums[j] 在 dp 中的 upper_bound 位置 lower_bound 位置 - upper_bound 位置指的是序列中第一个大于 nums[j] 的元素所在的位置 - lower_bound 位置指的是序列中第一个大于等于 nums[j] 的元素所在的位置 - C++ 中分别实现了 upper_bound 和 lower_bound，定义在 <algorithm> 中 - 如果在末尾，则插入；反之则替换 - upper_bound 只能用于不存在重复元素的情况；而 lower_bound 可以兼容两种情况

  • Code 
    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
    34
    35
    36
    37
    38
    39
    40
    // 牛客网
    class AscentSequence {
    public:
        int findLongest(const vector<int>& nums, int n) {
            vector<int> dp;

            for (int j = 0; j < n; j++) {
                // 这里用 upper_bound 也可以
                auto it = lower_bound(dp.begin(), dp.end(), nums[j]);
                if (it == dp.end())
                    dp.push_back(nums[j]);
                else
                    *it = nums[j];
            }

            return dp.size();
        }
    };

    // LeetCode
    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            int n = nums.size();
            vector<int> dp;

            for (int j = 0; j < n; j++) {
                // 这里只能使用 lower_bound
                auto it_l = lower_bound(dp.begin(), dp.end(), nums[j]);
                // auto it_u = upper_bound(dp.begin(), dp.end(), nums[j]);
                
                if (it_l == dp.end())
                    dp.push_back(nums[j]);
                else
                    *it_l = nums[j];
            }

            return dp.size();
        }
    };

最长回文子序列

最长回文子序列 - LeetCode

问题描述 

1
2
3
4
5
6
7
8
给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。

示例 1:
  输入:
    "bbbab"
  输出:
    4
  一个可能的最长回文子序列为 "bbbb"。

思路 - 相比最长回文子串，最长回文子序列更像最长公共子序列，只是改变了循环方向 - DP 定义 - 记 s[i:j] := 字符串 s 在区间 [i:j] 上的子串 - 定义 dp[i][j] := s[i:j] 上回文序列的长度 - DP 初始化 

1
dp[i][i]   = 1  // 单个字符也是一个回文序列
- DP 更新 
1
2
3
4
5
6
7
dp[i][j] = dp[i+1][j-1] + 2,              if s[i] == s[j]
         = max(dp[i+1][j], dp[i][j-1]),   else

比较一下 LCS 的递推公式
dp[i][j] = 0                              当 i=0 或 j=0 时
         = dp[i-1][j-1] + 1               当 `s1[i-1] == s2[j-1]` 时
         = max(dp[i-1][j], dp[i][j-1])    当 `s1[i-1] != s2[j-1]` 时
- Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.length();

        vector<vector<int>> dp(n, vector<int>(n, 0));
        
        for (int i = 0; i < n; i++)
            dp[i][i] = 1;
        
        for (int j = 1; j < n; j++)             // 子串结束位置
            for (int i = j-1; i >=0; i--) {     // 子串开始位置
                if (s[i] == s[j])
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                else
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }

        return dp[0][n - 1];
    }
};

最长回文子串

最长回文子串_牛客网

最长回文子串 - LeetCode > 牛客网只需要输出长度；LeetCode 还需要输出一个具体的回文串

问题描述 

1
2
3
4
5
6
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

示例 1：
  输入: "babad"
  输出: "bab"
  注意: "aba"也是一个有效答案。

思路 - O(N^2) - DP 定义 - 记 s[i:j] := 字符串 s 在区间 [i:j] 上的子串 - 定义 dp[i][j] := s[i:j] 是否是一个回文串 - DP 初始化 

1
dp[i][i]   = 1  // 单个字符也是一个回文串
- DP 更新 
1
2
3
4
5
6
7
8
9
10
dp[i][j] = dp[i+1][j-1],  if s[i] == s[j]
         = 0,             else

注意到：如果 j - i < 2 的话（比如 j=2, i=1），dp[i+1][j-1]=dp[2][1] 会出现不符合 DP 定义的情况
所以需要添加边界条件
  
  dp[i][i+1] = 1,  if s[i] == s[i+1]
             = 0,  else
  
该边界条件可以放在初始化部分完成；但是建议放在递推过程中完成过更好（为了兼容牛客和LeetCode）
- Code 
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// 牛客网 AC
class Palindrome {
public:
    int getLongestPalindrome(const string& s, int n) {
        vector<vector<int> > dp(n, vector<int>(n, 0));
        
        // 初始化
        for (int i=0; i<n-1; i++)
            dp[i][i] = 1;
        
        int len = 1;
        for (int j=1; j<n; j++) {         // 子串结束位置
            for (int i=j-1; i>=0; i--) {  // 子串开始位置
                if (j-i < 2)
                    dp[i][j] = (s[i]==s[j]) ? 1 : 0;
                else if (s[i]==s[j])
                    dp[i][j] = dp[i+1][j-1];
                else
                    dp[i][j] = 0;  // 因为 dp 全局初始化就是 0，这里其实可以不写
                
                if (dp[i][j] && j-i+1 > len)
                    len = j-i+1;
            }
        }
        
        return len;
    }
};

// LeetCode - 只要添加一个记录开始位置的变量即可
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();

        vector<vector<int> > dp(n, vector<int>(n, 0));

        // 初始化
        for (int i=0; i<n-1; i++)
            dp[i][i] = 1;

        int len = 1;
        int beg = 0;    // 记录开始位置
        for (int j=1; j<n; j++) {         // 子串结束位置
            for (int i=j-1; i>=0; i--) {  // 子串开始位置
                if (j-i < 2)
                    dp[i][j] = (s[i]==s[j]) ? 1 : 0;
                else if (s[i]==s[j])
                    dp[i][j] = dp[i+1][j-1];
                else
                    dp[i][j] = 0;  // 因为 dp 全局初始化就是 0，这里其实可以不写

                if (dp[i][j] && j-i+1 > len) {
                    beg = i;  // 保存开始位置
                    len = j-i+1;
                }

            }
        }

        return s.substr(beg, len);  // 截取子串
    }
};

Manacher 算法 - O(N) > 算法-最长回文子串(Manacher算法) - 琼珶和予 - 博客园

最大连续子序列和

最大连续子序列_牛客网 > 牛客网要求同时输出最大子序列的首尾元素

思路 - 基本问题：只输出最大连续子序列和 - DP 定义 - 记 a[0:i] := 序列 a 在区间 [0:i] 上的子序列 - 定义 dp[i] := a[0:i] 上的最大子序列和 - 实际并没有严格按照上面的定义，中间使用一个变量记录当前全局的最大连续子序列和 - DP 初始化 
1
dp[0] = a[0]
- DP 更新 
1
2
3
4
5
6
// 只要 dp[i] > 0 就一直累加下去，一旦小于 0 就重新开始
dp[i] = dp[i-1] + a[i],     if dp[i-1] > 0
      = a[i],               else

ret = max{ret, dp[i]}       // 只要大于 0 就累加会导致 dp[i] 保存的并不是 a[0:i] 中的最大连续子序列和
                            // 所以需要一个变量保存当前全局的最大连续子序列和

直观实现-无优化-空间复杂度O(N)（点击展开）

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
34
35
36
void foo() {
    int n;
    while (cin >> n) {
        vector<int> a(n);
        for (int i = 0; i<n; i++)
            cin >> a[i];

        vector<int> dp(n);
        dp[0] = a[0];

        int ret = a[0];
        for (int i = 1; i < n; i++) {
            if (dp[i - 1] > 0)
                dp[i] = dp[i - 1] + a[i];
            else
                dp[i] = a[i];

            ret = max(ret, dp[i]);
        }
        cout << ret << endl;
    }
}
/*
输入
5
1 5 -3 2 4
6
1 -2 3 4 -10 6
4
-3 -1 -2 -5

输出
9
7
-1
*/

  • DP 优化

    注意到每次递归实际只用到了 dp[i-1]，实际只要用到一个变量，空间复杂度 O(1) 

    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
    void foo2() {
        int n;
        while (cin >> n) {
            vector<int> a(n);
            for (int i = 0; i<n; i++)
                cin >> a[i];

            int ret = INT_MIN;
            int max_cur = 0;

            for (int i = 0; i < n; i++) {
                if (max_cur > 0)       // 如果大于 0 就一直累加
                    max_cur += a[i];
                else                   // 一旦小于 0 就重新开始
                    max_cur = a[i];

                if (max_cur > ret)     // 保存找到的最大结果
                    ret = max_cur;

                // 以上可以简写成下面两行代码
                //max_cur = max(max_cur + a[i], a[i]);
                //ret = max(ret, max_cur);
            }
            cout << ret << endl;
        }
    }

思路 - 输出区间/首尾 - 增加两个变量即可 - 注意：题目要求，如果序列中全是负数，则输出 0，以及整个序列的首尾元素 

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// 牛客网 AC
#include <iostream>
#include <cstdio>
#include <vector>
#include <climits>

using namespace std;

void foo3() {
    int n;
    while (cin >> n && n) {
        vector<int> a(n);
        for (int i = 0; i<n; i++)
            cin >> a[i];

        int ret = INT_MIN;
        int max_cur = 0;
        int beg = a[0], end = a[n-1];  // 输出首尾
        // int beg = 0, end = n-1;     // 输出区间

        int tmp_beg;  // 保存临时 beg
        for (int i = 0; i < n; i++) {
            if (max_cur > 0) {
                max_cur += a[i];
            }
            else {
                max_cur = a[i];
                tmp_beg = a[i];
                // tmp_beg = i;
            }

            if (max_cur > ret) {  // > 表明保存的是第一次出现的最大和，>= 则为最后一次（未验证）
                ret = max_cur;
                beg = tmp_beg;
                end = a[i];  // 输出首尾
                // end = i;  // 输出区间
            }
        }

        if (ret < 0) 
            printf("%d %d %d\n", 0, a[0], a[n-1]);
            // printf("%d %d %d\n", 0, 0, n-1);
        else
            printf("%d %d %d\n", ret, beg, end);
    }
}

int main() {
    foo3();
    return 0;
}

编辑距离

LeetCode-编辑距离

问题描述 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：
  插入一个字符
  删除一个字符
  替换一个字符

示例:
  输入: word1 = "horse", word2 = "ros"
  输出: 3
  解释: 
  horse -> rorse (将 'h' 替换为 'r')
  rorse -> rose (删除 'r')
  rose -> ros (删除 'e')
- 注意：编辑距离指的是将 word1 转换成 word2

思路 - 用一个 dp 数组维护两个字符串的前缀编辑距离 - DP 定义 - 记 word[0:i] := word 长度为 i 的**前缀子串** - 定义 dp[i][j] := 将 word1[0:i] 转换为 word2[0:j] 的操作数 - 初始化 

1
2
dp[i][0] = i  // 每次从 word1 删除一个字符
dp[0][j] = j  // 每次向 word1 插入一个字符
- 递推公式 - word1[i] == word1[j] 时 
1
dp[i][j] = dp[i-1][j-1]
- word1[i] != word1[j] 时，有三种更新方式，取最小 
1
2
3
4
// word[1:i] 表示 word 长度为 i 的前缀子串
dp[i][j] = min({ dp[i-1][j]   + 1 ,     // 将 word1[1:i-1] 转换为 word2[1:j] 的操作数 + 删除 word1[i] 的操作数(1)
                 dp[i][j-1]   + 1 ,     // 将 word1[0:i] 转换为 word2[0:j-1] 的操作数 + 将 word2[j] 插入到 word1[0:i] 之后的操作数(1)
                 dp[i-1][j-1] + 1 })    // 将 word1[0:i-1] 转换为 word2[0:j-1] 的操作数 + 将 word1[i] 替换为 word2[j] 的操作数(1)
×