Algorithm
lc132_分割回文串 II
思路:
子分隔需要最优情况才能汇聚成母分隔。因此可能需要一些其他思路才能判断最小分隔数。
贪心获取最长回文，然后不断贪心，然后再反向也贪心一次。
看题解才知道可以遍动态规划子状态。并且能用如此方法预计算回文串，学习。
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
|
class Solution {
public:
int minCut(string s) {
int n = s.size();
vector<vector<int>> g(n, vector<int>(n, true));
/* 为什么 i 要倒序？因为动态规划中 g[i][j] 依赖于 g[i + 1][j - 1]，
外层循环倒序（i 从 n-1 到 0）保证了当计算 g[i][j] 时，
所需的 g[i + 1][j - 1] 已在前面的迭代中计算完毕，满足依赖顺序。 */
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
g[i][j] = (s[i] == s[j]) && g[i + 1][j - 1];
}
}
vector<int> f(n, INT_MAX);
for (int i = 0; i < n; ++i) {
if (g[0][i]) {
f[i] = 0;
}
else {
for (int j = 0; j < i; ++j) {
if (g[j + 1][i]) {
f[i] = min(f[i], f[j] + 1);
}
}
}
}
return f[n - 1];
}
};
|
Review
加密货币如何帮助初创企业赢得投资？【TED演讲】
小公司联合一起ICO。VCs也能省去中介费，直接投资获得可交易股权。
Tips
高性能并行文件系统 3FS
Share
Roam连接全球网络,引领AI数据革命