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

问题描述

1. 对于一个给定的字符串，给定策略以最少次数将其分割成一些子串，使得某个子串都是回文串。

2. 某公司拟在某市开一些分公司，公司分布在不同街道，街道结构可以用一棵树来进行表达。为了避免分公司间竞争冲突，两个分公司不允许开在相邻的街道。

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

   • 分公司开在不同街道产生的效益不同；

   请分别设计策略使得所开分公司产生的价值最大。

解题思路

T1

1. 简单编写一个isPalindrome 函数用于判断给定字符串中从 start 到 end 索引范围内的子串是否为回文串。它通过比较首尾字符，逐步向中间移动来进行判断。

2. minCut 函数接收一个字符串 s 作为输入，然后使用动态规划来计算每个子串的最少分割次数。

3. 首先，定义了一个长度为 n 的动态规划数组 dp，其中 dp[i] 表示 s[0:i] 子串的最少分割次数。

4. 然后，对于字符串中的每个位置 i，判断 s[0:i] 是否为回文串。如果是，说明整个子串已经是回文串，不需要分割，因此 dp[i] 直接设置为 0。

5. 如果 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] 表示已知的最少分割次数。

6. 最后，返回 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. 若分公司开在不同街道产生的效益相同

1. 状态定义：代码中使用了一个二维数组 dp[i][2] 来表示每个街道的状态，其中 dp[i][0] 表示不选择第 i 个街道时的最大收益，dp[i][1] 表示选择第 i 个街道时的最大收益。

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

3. 最终结果：最后，根据根节点的 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，父节点为-1
    cout << "最大收益为：" << result << endl;
    return 0;
}

运行结果

最大收益为：17