【算法作业】最少分割回文字符串，开设分公司

问题描述

对于一个给定的字符串，给定策略以最少次数将其分割成一些子串，使得某个子串都是回文串。
某公司拟在某市开一些分公司，公司分布在不同街道，街道结构可以用一棵树来进行表达。为了避免分公司间竞争冲突，两个分公司不允许开在相邻的街道。
- 若分公司开在不同街道产生的效益相同；
- 分公司开在不同街道产生的效益不同；
请分别设计策略使得所开分公司产生的价值最大。

解题思路

T1

简单编写一个isPalindrome 函数用于判断给定字符串中从 start 到 end 索引范围内的子串是否为回文串。它通过比较首尾字符，逐步向中间移动来进行判断。
minCut 函数接收一个字符串 s 作为输入，然后使用动态规划来计算每个子串的最少分割次数。
首先，定义了一个长度为 n 的动态规划数组 dp，其中 dp[i] 表示 s[0:i] 子串的最少分割次数。
然后，对于字符串中的每个位置 i，判断 s[0:i] 是否为回文串。如果是，说明整个子串已经是回文串，不需要分割，因此 dp[i] 直接设置为 0。
如果 s[0:i] 不是回文串，则需要考虑如何进行分割。遍历 0 到 i-1 的位置 j，如果 s[j+1:i] 是回文串，那么可以尝试将 s[0:i] 分割成 s[0:j] 和 s[j+1:i] 两个部分，其中 s[0:j] 可以使用 dp[j] 表示已知的最少分割次数。
最后，返回 dp[n-1]，即整个字符串的最少分割次数。

这个算法的时间复杂度是 O( $n^2$ )，其中 n 是字符串的长度，因为需要遍历每个位置来计算最少分割次数。

T2

这个题目要求抽象出一个树，我们可以把街道当成点，街道相邻就指这个树的边。

例如用下面这个邻接矩阵来表示这棵树。

	0	1	2	3	4	5	6	7	8	9
0		1	1
1	1			1	1
2	1					1	1
3		1						1	1
4		1								1
5			1
6			1
7				1
8				1
9					1

1. 若分公司开在不同街道产生的效益相同

状态定义：代码中使用了一个二维数组 dp[i][2] 来表示每个街道的状态，其中 dp[i][0] 表示不选择第 i 个街道时的最大收益，dp[i][1] 表示选择第 i 个街道时的最大收益。
动态规划：代码中采用了自底向上的动态规划方法。从树的叶子节点开始向上递推，计算每个节点的最大收益。对于每个节点 i，根据其子节点的状态来更新 dp[i][0] 和 dp[i][1]。如果选择了节点 i，则不能选择其相邻的节点，因此 dp[i][1] 的值就是 value[i] 加上所有不选择相邻节点时的最大收益之和。而 dp[i][0] 则是选择与不选择 i 中收益较大的一个。
最终结果：最后，根据根节点的 dp[0][0] 和 dp[0][1] 中的较大值，即可确定最大收益。

结合了动态规划和树形结构的特点，通过状态转移的方式有效地解决了在树形结构中选择最优解的问题。第一道题其实就是在求解最大独立集问题。时间复杂度为 O( $N^2$ )

2. 若分公司开在不同街道产生的效益不同

其实在动态规划算法下，这两个题目几乎没有区别。

街道编号	0	1	2	3	4	5	6	7	8	9
街道价值	1	1	3	5	2	3	1	4	3	5

只需要把选择加入dp数组的节点的cnt改成sum，转为累计价值，而不是个数就行了。

完整代码

T1

#include <iostream>
#include <vector>
#include <string>
#include <climits>using namespace std;// 辅助函数，判断一个子串是否为回文串
bool isPalindrome(const string& s, int start, int end) {while (start < end) {if (s[start] != s[end])return false;start++;end--;}return true;
}int minCut(string s) {int n = s.length();if (n <= 1) return 0;// dp[i] 表示 s[0:i] 子串的最少分割次数vector<int> dp(n, INT_MAX);for (int i = 0; i < n; ++i) {if (isPalindrome(s, 0, i)) {dp[i] = 0; // 整个子串是回文串，不需要分割} else {for (int j = 0; j < i; ++j) {if (isPalindrome(s, j + 1, i)) {// 如果 s[j+1:i] 是回文串，则可以尝试更新 dp[i] 的值dp[i] = min(dp[i], dp[j] + 1);}}}}return dp[n - 1];
}int main() {string s = "abababbbbba";cout << "最少分割次数为：" << minCut(s) << endl;return 0;
}

运行结果

最少分割次数为：2

T2

1. 若分公司开在不同街道产生的效益相同

#include <iostream>using namespace std;// 定义树的节点数
const int N = 10;// 树的邻接矩阵，1 表示节点之间有边相连，0 表示没有边相连
int tree[N][N] = {{0, 1, 1, 0, 0, 0, 0, 0, 0, 0},{1, 0, 0, 1, 1, 0, 0, 0, 0, 0},{1, 0, 0, 0, 0, 1, 1, 0, 0, 0},{0, 1, 0, 0, 0, 0, 0, 1, 1, 0},{0, 1, 0, 0, 0, 0, 0, 0, 0, 1},{0, 0, 1, 0, 0, 0, 0, 0, 0, 0},{0, 0, 1, 0, 0, 0, 0, 0, 0, 0},{0, 0, 0, 1, 0, 0, 0, 0, 0, 0},{0, 0, 0, 1, 0, 0, 0, 0, 0, 0},{0, 0, 0, 0, 1, 0, 0, 0, 0, 0}
};// 动态规划求解最多可以开几个分公司
int dp[N][2]; // dp[i][0]表示不选节点i的最大独立集大小，dp[i][1]表示选节点i的最大独立集大小int maxCompanies() {// 根据邻接矩阵进行动态规划for (int i = N - 1; i >= 0; --i) {int cnt0 = 0, cnt1 = 1;for (int j = i + 1; j < N; ++j) {if (tree[i][j]) {cnt0 += max(dp[j][0], dp[j][1]);cnt1 += dp[j][0];}}dp[i][0] = cnt0;dp[i][1] = cnt1;}return max(dp[0][0], dp[0][1]);
}int main() {int result = maxCompanies();cout << "最多可以开的分公司数量为：" << result << endl;return 0;
}

运行结果

最多可以开的分公司数量为：6

2. 若分公司开在不同街道产生的效益不同

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;const int N = 10;// 街道价值
int value[N] = {1, 1, 3, 5, 2, 3, 1, 4, 3, 5};// 树的邻接矩阵
int tree[N][N] = {{0, 1, 1, 0, 0, 0, 0, 0, 0, 0},{1, 0, 0, 1, 1, 0, 0, 0, 0, 0},{1, 0, 0, 0, 0, 1, 1, 0, 0, 0},{0, 1, 0, 0, 0, 0, 0, 1, 1, 0},{0, 1, 0, 0, 0, 0, 0, 0, 0, 1},{0, 0, 1, 0, 0, 0, 0, 0, 0, 0},{0, 0, 1, 0, 0, 0, 0, 0, 0, 0},{0, 0, 0, 1, 0, 0, 0, 0, 0, 0},{0, 0, 0, 1, 0, 0, 0, 0, 0, 0},{0, 0, 0, 0, 1, 0, 0, 0, 0, 0}
};int dp[N][2]; // dp[i][0]表示不选择节点i时的最大收益，dp[i][1]表示选择节点i时的最大收益int maxProfit(int node, int parent) {int sum0 = 0, sum1 = value[node];for (int i = 0; i < N; ++i) {if (tree[node][i] && i != parent) {maxProfit(i, node);sum1 += dp[i][0];sum0 += max(dp[i][0], dp[i][1]);}}dp[node][0] = sum0;dp[node][1] = sum1;return max(sum0, sum1);
}int main() {int result = maxProfit(0, -1); // 根节点为0，父节点为-1cout << "最大收益为：" << result << endl;return 0;
}

运行结果