0%

dp困难专题

leetcode 1411. 给 N x 3 网格图涂色的方案数

你有一个 $n * 3$ 的网格图 $grid$ ,你需要用 红,黄,绿 三种颜色之一给每一个格子上色,且确保相邻格子颜色不同(也就是有相同水平边或者垂直边的格子颜色不同)。给你网格图的行数 $n$ 请你返回给 $grid$ 涂色的方案数。由于答案可能会非常大,请你返回答案对 $10^9 + 7$ 取余的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
示例 1

输入:n = 1
输出:12
解释:总共有 12 种可行的方法:

示例 2

输入:n = 2
输出:54
示例 3

输入:n = 3
输出:246
示例 4

输入:n = 7
输出:106494
示例 5

输入:n = 5000
输出:30228214

提示:

  1. $n == grid.length$
  2. $grid[i].length == 3$
  3. $1 <= n <= 5000$

思路:状态表示:$f[i][j]$ 表示第 $i$ 行以 $j$ 涂色的方案数,那么第一个问题就是涂色怎么表示呢?将红黄绿看成是 $012_3$ ,所以我们可以用一个三进制数去表示这一行的涂色情况。
答案:$\sum_{i=1}^T(f[n][i])$, $T$ 是只有一行的总涂色数
状态转移:$f[i][j] += f[i-1][k]$ 既将与上一行涂色情况不冲突的所有方案数累加即可。
预处理:只有一行时,将合法的方案用一个数组types存起来,然后将所有不冲突的行的涂色情况用legal数组标记出来。

  • 时间复杂度:$O(T^2 * n)$
  • 空间复杂度:$O(T^2 + n * T)$
    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
    class Solution {
    public:
    int numOfWays(int n) {
    int mod = 1e9 + 7, res = 0;
    vector<int> types;
    //求出第一行所有涂色方案表示
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    for(int k=0;k<3;k++)
    if(i != j && j != k) types.push_back(9 * i + 3 * j + k);

    int t = types.size();
    vector<vector<int>> legal(t, vector<int>(t));
    //标记所有不冲突的上下行
    for(int i=0;i<t;i++) {
    int x1 = types[i] / 9, x2 = types[i] / 3 % 3, x3 = types[i] % 3;
    for(int j=0;j<t;j++) {
    int y1 = types[j] / 9, y2 = types[j] / 3 % 3, y3 = types[j] % 3;
    if(x1 != y1 && x2 != y2 && x3 != y3) legal[i][j] = 1;
    }
    }

    vector<vector<int>> f(n + 1, vector<int> (t));
    //初始化,第一行所有涂色方案数都为1
    for(int i=0;i<t;i++) f[1][i] = 1;

    for(int i=2;i<=n;i++) {
    for(int j=0;j<t;j++) {
    for(int k=0;k<t;k++) {
    if(legal[k][j]) f[i][j] = (f[i][j] + f[i-1][k]) % mod;
    }
    }
    }

    for(int i=0;i<t;i++) res = (res + f[n][i]) % mod;
    return res;
    }
    };

leetcode 1278. 分割回文串 III

给你一个由小写字母组成的字符串 $s$ ,和一个整数 $k$ 。
请你按下面的要求分割字符串:
首先,你可以将 $s$ 中的部分字符修改为其他的小写英文字母。
接着,你需要把 $s$ 分割成 $k$ 个非空且不相交的子串,并且每个子串都是回文串。
请返回以这种方式分割字符串所需修改的最少字符数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例 1

输入:s = "abc", k = 2
输出:1
解释:你可以把字符串分割成 "ab""c",并修改 "ab" 中的 1 个字符,将它变成回文串。
示例 2

输入:s = "aabbc", k = 3
输出:0
解释:你可以把字符串分割成 "aa""bb""c",它们都是回文串。
示例 3

输入:s = "leetcode", k = 8
输出:0

提示:

  • $1 <= k <= s.length <= 100$
  • $s 中只含有小写英文字母。$

思路:
状态定义:$f[i][j]$表示将s前i个字符分成j部分每个子串都是回文串的最少修改次数
答案:$f[n-1][k]$
状态转移:$f[i][j] = min(f[i][j], f[k][j-1] + g[k+1][j])$
即每次将$k+1\sim i$ 这一段当成最后一段,找出所有情况中的最佳划分即可
$g[i][j]$ 表示将 $i\sim j$ 变成回文串的最小修改次数

  • 时间复杂度:$O(n^2*k)$
  • 空间复杂度:$O(n^2 + 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
    24
    25
    26
    class Solution {
    public:
    int palindromePartition(string s, int k) {
    int n = s.size();
    //g[i][j]表示将i~j变成回文串的最小修改次数
    vector<vector<int>> g(n, vector<int>(n));
    for(int len=2;len<=n;len++) {
    for(int i=0;i+len-1<n;i++) {
    int j = i + len - 1;
    if(s[i] == s[j]) g[i][j] = g[i+1][j-1];
    else g[i][j] = g[i+1][j-1] + 1;
    }
    }

    vector<vector<int>> f(n, vector<int>(k + 1, 0x3f3f3f3f));
    for(int i=0;i<n;i++) f[i][1] = g[0][i];
    for(int i=0;i<n;i++) {
    for(int j=2;j<=k;j++) {
    for(int p=0;p<i;p++) {
    f[i][j] = min(f[i][j], f[p][j-1] + g[p+1][i]);
    }
    }
    }
    return f[n-1][k];
    }
    };

leetcode 1312. 让字符串成为回文串的最少插入次数

给你一个字符串 $s$ ,每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 $s$ 成为回文串的 最少操作次数 。
「回文串」是正读和反读都相同的字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
示例 1

输入:s = "zzazz"
输出:0
解释:字符串 "zzazz" 已经是回文串了,所以不需要做任何插入操作。
示例 2

输入:s = "mbadm"
输出:2
解释:字符串可变为 "mbdadbm" 或者 "mdbabdm"
示例 3

输入:s = "leetcode"
输出:5
解释:插入 5 个字符后字符串变为 "leetcodocteel"
示例 4

输入:s = "g"
输出:0
示例 5

输入:s = "no"
输出:1

提示:

  1. $1 <= s.length <= 500$
  2. $s 中所有字符都是小写字母$

思路:简单水题,求解最长回文子序列的变形,答案就是字符串总长度减去最长回文子序列的长度

  • 时间复杂度:$O(n^2)$
  • 空间复杂度:$O(n^2)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int minInsertions(string s) {
int n = s.size();
//求解最长回文子序列
vector<vector<int>> f(n, vector<int>(n));
for(int i=0;i<n;i++) f[i][i] = 1;
for(int len=2;len<=n;len++) {
for(int i=0;i+len-1<n;i++) {
int j = i + len - 1;
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 n - f[0][n-1];
}
};

leetcode 1611. 使整数变为 0 的最少操作次数

给你一个整数 $n$,你需要重复执行多次下述操作将其转换为 $0$ :

翻转 $n$ 的二进制表示中最右侧位(第 $0$ 位)。
如果第 $(i-1)$ 位为 $1$ 且从第 $(i-2)$ 位到第 $0$ 位都为 $0$,则翻转 $n$ 的二进制表示中的第 $i$ 位。
返回将 $n$ 转换为 $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
示例 1

输入:n = 0
输出:0
示例 2

输入:n = 3
输出:2
解释:3 的二进制表示为 "11"
"11" -> "01" ,执行的是第 2 种操作,因为第 0 位为 1
"01" -> "00" ,执行的是第 1 种操作。
示例 3

输入:n = 6
输出:4
解释:6 的二进制表示为 "110".
"110" -> "010" ,执行的是第 2 种操作,因为第 1 位为 1 ,第 00 位为 0
"010" -> "011" ,执行的是第 1 种操作。
"011" -> "001" ,执行的是第 2 种操作,因为第 0 位为 1
"001" -> "000" ,执行的是第 1 种操作。
示例 4

输入:n = 9
输出:14
示例 5

输入:n = 333
输出:393

提示:

  1. $0 <= n <= 10^9$

思路:很有意思的一道题,其实是求格雷码的逆变换,本题从格雷码生成开始分析。
格雷码就是 $1\sim n$ 的一个排列中,相邻的两个数字的二进制表示只有一位不同。
如三位的格雷码:中间列是序号,左三位是三位格雷码的二进制表示,右三位是序号的二进制表示。
生成方式1.
(1)反转前一个格雷码的二进制位的最后一位
(2)将右边第一个二进制位是1的位置的左边的二进制位翻转
具体看以下样例
0 0 0 –0–> 0 0 0
0 0 1 –1–> 0 0 1
0 1 1 –2–> 0 1 0
0 1 0 –3–> 0 1 1
1 1 0 –4–> 1 0 0
1 1 1 –5–> 1 0 1
1 0 1 –6–> 1 1 0
1 0 0 –7–> 1 1 1

生成方式2.
显然:上述格雷码 $G(n)$ 和 $n$ 是有关系的, $G(n)$ 的二进制位表示中第 $i$ 位为 $1$ 只有两种情况(二进制位右边为最低位,左边为最高位),序号 $n$ 的二进制表示中第 $i$ 位为 $1$ ,第 $i+1$ 位为 $0$ ,或者第 $i$ 位为 $0$ ,第 $i+1$ 位为 $1$ ,所以是个异或的过程,即 $G(n) = n \bigoplus (n >> 1)$

完成生成格雷码的过程后,再来看其逆变换的过程,从高位到低位有:

$n_k = g_k$
$n_{k-1} = g_{k-1} \bigoplus n_k = g_{k-1} \bigoplus g_k$
$n_{k-2} = g_{k-2} \bigoplus n_{k-1} = g_{k-2} \bigoplus g_{k-1} \bigoplus g_{k}$

$n_{k-j} = \bigoplus_{i=0}^j g_{k-i}$
所以其逆变换从最高位开始递推有:

1
2
3
4
5
int minimumOneBitOperations(int g) {
int n = 0;
for(;g;g>>=1) n^=g;
return n;
}
  • 时间复杂度:$O(log_n)$
  • 空间复杂度:$O(1)$
    1
    2
    3
    4
    5
    6
    7
    8
    class Solution {
    public:
    int minimumOneBitOperations(int n) {
    int g = 0;
    for(;n;n>>=1) g^=n;
    return g;
    }
    };