动态规划专题

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)




评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×