单序列型 DP

LC 300 最长递增子序列(LIS)

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1:

输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。

示例 2:

输入:nums = [0,1,0,3,2,3]
输出:4

示例 3:

输入:nums = [7,7,7,7,7,7,7]
输出:1

分析:

自然想到定义 $f (i)$ 表示切片以 v [i] 结尾的 LIS。举个例子:

i  0 1 2 3 4 5
v  4 0 6 1 2 3
f  1 1 2 2 3 4

注意到计算过程为(以 $i=3$ 为例)

f (3) = ? 不知道
注意到最后一个满足 v [3] > v [k] 的 k 是 k = 1
于是 f (3) = f (1) + 1

总结:$f (i) = f (k) + 1$,其中 $k$ 为:满足 $k < i$ 且 $v [k] < v [i]$ 的,最大的 f [k] 所对应的 k

  • $k < i$ 是切片约束。
  • $v [k] < v [i]$ 是递增约束
  • 最大的 f [k] 所对应的 k 是最长子序列约束

初始条件:f [0] = 1

参考代码:

class Solution {
public:
  int find_k(std::vector<int> &v, std::vector<int> &dp, int i) {
    int max_vk = -1;
    int find_k = -1;
    for (int k = 0; k < i; k++) {
      if (v[k] < v[i] && dp[k] > max_vk) {
        max_vk = dp[k];
        find_k = k;
      }
    }
    return find_k;
  }
  int lengthOfLIS(vector<int> &v) {
    auto n = v.size();
    //dp [i] 表示以 v [i] 结尾的 v [0:i] 的 LIS
    std::vector<int> dp(n);
    dp[0] = 1;
    auto llis = 1;
    for (int i = 1; i < n; i++) {
      auto k = find_k(v, dp, i);
      if (k == -1) {
        dp[i] = 1;
      } else {
        dp[i] = dp[k] + 1;
      }
      printf("dp = ");
      print_vec(dp);
      llis = max(dp[i], llis);
    }
    return llis;
  }
};

参考代码 2:

class Solution {
public:
  int lengthOfLIS(vector<int> &v) {
    auto n = v.size();
    if (n == 0)
      return 0;
    std::vector<int> dp(n);
    dp[0] = 1;
    int llis = 1;
    for (int i = 1; i < n; i++) {
      dp[i] = 1;
      for (int k = 0; k < i; k++) {
        if (v[k] < v[i]) {
          dp[i] = max(dp[i], dp[k] + 1);
        }
      }
      print_vec(dp);
      llis = max(llis, dp[i]);
    }
    return llis;
  }
};

Game of 5 Powers

You are given a string S that consists of characters ‘0’ and ‘1’ only. Return the smallest positive integer K such that it is possible to cut S into K pieces, each of them being a power of 5 (no leading zeros). If there is no such K, return -1 instead.

e.g. S=“101101101" return3 (101 = 5)

e.g. S=“1111101”return 1 (1111101 = 125)

e.g. S =“0000”return -1

e.g. S=“100" return -1

即输入 01 串,我们要将这个串分为几个部分,每个部分都是 $5^n$,返回最小的划分次数。例如 1011111101,可以划分为 101 1111101,所以返回 2.

分析:

为了保证尽量小,我们要让划分中所含的数字尽量大。

i  0 1 2 3 4 ............ n-1
v  1 0 1 0 0 ........... 0 1

我们可以采用插空法,定义 f (i) 为在 i 出分割的最小划分。

举个例子,对于 101101101,空格表示切割位置

i = 0, f (101101101)	可以,因为 101101101 不是 5^n
i = 1, 1 f (01101101) 不行,因为 1 不是 5^n
...
i = 3,101 f (101101) 可以,因为 101 是 5^n

即我们要确保分割的前一部分是 5^n,同时后一部分通过迭代算出。

参考代码:

bool isPowerOf5(string str){
	if(str[0] == '0') 
		return false;
	long num = 0;
	for (char s : str){
		num << 1;
		if(s == '1') 
			num++;
	}
	while(num % 5 == 0) num/=5;
	return num == 1;
}

int solve(string str) {
	int n = str.size();
	vector<int> dp(n);
	fill(dp.begin(), dp.end(), -1);
	for (int i = 0; i < n; i++){
		if(isPowerOf5(substring(str, 0, i+1))) {
			dp[i] = 1;
			continue;
		}
		for (int j = 0; j < i; j++) {
			string last = substring(str, j+1, i+1);
			if(dp[j] == -1 || !isPowerOf5(last)) 
				continue;
			if(dp[i] == -1 || dp[i] > dp[j] + 1){
				dp[i] = dp[j] + 1;
			}
		}
	}
	return dp[n-1];
}

双序列型 DP

输入序列为两个数组。$f (i,j)$ 表示输入为 $A [0:i], B [0:j]$ 时的状态,建立其与 $f (i-1,j),f (i-1,j-1),f (i,j-2),f (i-2,j),f (i-2,j-1)$ 等所有更小的情况的关系。

LC 1143. 最长公共子序列(LCS)

定义 $f (i,j)$ 表示 A [0:i], B [0:j] 的 LCS。

考虑 A [i] != B [j],即最后一个字符不相等,那么我们只能拿掉一个字符比较。可以从 A 拿,也可以从 B 拿。即 $f (i,j) = \max \{f (i-1,j),f (i,j-1)\}$.

考虑 A [i] == B [j],即最后一个匹配,则只要看除去最后一个字符的剩余前面部分是否匹配,即 $f (i,j) = f (i-1,j-1)+1$

然后考虑起始值:$f (0,j) = 0$ $f (i,0) = 0$。据此写代码:

class Solution {
public:
  int longestCommonSubsequence(string a, string b) {
    auto n = a.size(), m = b.size();
    vector<vector<int>>
        dp (n + 1,vector<int>(m + 1, 0)); // 注意 dp 数组的大小不是 nxm
    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 - 1][j], dp[i][j - 1]);
        }

        print_vec_2d(dp);
      }
    }
    return dp[n][m];
  }
};

下面考虑空间优化。

注意到只依赖 dp [i-1][j-1],即我们总是关注 2x2 的局部。所以可以对此优化。但是我们无法优化到 $O (1)$,这是因为虽然我们在 b 的循环中只引用了 i-1, j-1,然而 i-1 却是属于上一行的,我们必须保存一整行的数据。其实看计算次序(红箭头画出)就知道:

image-20211113235417281

因此我们必须记忆一整个 a 的行。而 b 相关的可以优化。

参考代码:

class Solution {
public:
  int longestCommonSubsequence(string a, string b) {
    auto n = a.size(), m = b.size();
    auto d = 2;
    vector<vector<int>> dp(d,
                           vector<int>(m + 1, 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 % d][j] = dp[(i - 1) % d][j - 1] + 1;
        } else {
          dp[i % d][j] = max(dp[(i - 1) % d][j], dp[i % d][j - 1]);
        }
      }
    }
    return dp[n % d][m];
  }
};

LC 300 最长递增子序列 的新解

我们可以把 A 先排序,然后计算 sortedA 与 A 的 LCS,即为 LIS 解。

LC 718. 最长公共字串

我们从最小情形考虑。举例 A=[12321], B=[32147],定义 $f (i,j)$ 表示 A [0:i], B [0:j] 的最长公共字串。

考虑 A [i] != B [j],即最后一个字符不相等,那么可以判定二者不交叉。即 $f (i,j) = 0$.

考虑 A [i] == B [j],即最后一个匹配,则只要看除去最后一个字符的剩余前面部分是否匹配,即 $f (i,j) = f (i-1,j-1)+1$

我的朴素解法:


class Solution {
public:
  int findLength(std::vector<int> &a, std::vector<int> &b) {
    auto n = a.size(), m = b.size();
    auto d = 2;
    int maxval = 0;
    vector<vector<int>> dp(d,
                           vector<int>(m + 1, 0)); // 注意 dp 数组的大小不是 nxm
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        if (a [i - 1] == b [j - 1]) { // 注意下标
          dp[i % d][j] = dp[(i - 1) % d][j - 1] + 1;
        }
        maxval = max(maxval, dp[i % d][j]);
      }
    }
    return maxval;
  }
};

但是我发现解并不是 dp [n][m],而是 dp 数组的最大值。(歪打正着)

老师的解法:

可以定义 $f (i,j)$ 为以 $A [i],B [j]$ 结尾的最长子串。代码就是我上面那样的了。

然后可以进一步空间优化。改成从右往左添加:

class Solution {
public:
  int findLength(std::vector<int> &a, std::vector<int> &b) {
    int n = a.size(), m = b.size(), maxval = 0;
    vector<int> dp(m + 1);
    for (int i = 1; i <= n; i++) {
      for (int j = m; j > 0; j--) {
        if (a [i - 1] == b [j - 1]) { // 注意下标
          dp[j] = dp[j - 1] + 1;
          maxval = max(maxval, dp[j]);
        }else{
          dp [j] = 0; // 这句不可少
        }        
      }
    }
    return maxval;
  }
};

矩阵坐标型 DP

背包型 DP

区间及其它类型 DP