一：乘积最大子数组

image-20251019214354549

1. 动态规划

该题的难点在于需要同时处理正值和负值，以x结尾的子串乘上下一个元素有可能继续增大，也有可能变得很小，但如果一个负数乘一个负数可能得出一个很大的结果，因此我们同时维护以x结尾的子串的最大值和最小值

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
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        vector<long long> maxM(nums.begin(), nums.end());
        vector<long long> minM(nums.begin(), nums.end());
        for (int i = 1; i < nums.size(); ++i)
        {
            maxM[i] = max(maxM[i - 1] * nums[i], max(minM[i - 1] * nums[i], static_cast<long long>(nums[i])));
            minM[i] = min(minM[i - 1] * nums[i], min(maxM[i - 1] * nums[i], static_cast<long long>(nums[i])));
        }
        return *max_element(maxM.begin(), maxM.end());
    }
};

// 滚动数组空间优化
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        long long maxM = nums[0];
        long long maxT = nums[0];
        long long minM = nums[0];
        long long minT = nums[0];
        long long ans = nums[0];
        for (int i = 1; i < nums.size(); ++i)
        {
            maxT = maxM, minT = minM;
            maxM = max(maxT * nums[i], max(minT * nums[i], static_cast<long long>(nums[i])));
            minM = min(minT * nums[i], min(maxT * nums[i], static_cast<long long>(nums[i])));
            ans = max(maxM, ans);
        }
        return static_cast<int>(ans);
    }
};

image-20251019214419857

二：分割等和子集

image-20251019214449089

1. 动态规划

该题使用二维数组来存储子序列能否目标值，除了前置条件，后一个的判断需要根据先前的结果来判断

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
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int len = nums.size();
        if (len < 2) return false;
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum & 1) return false;
        int target = sum / 2;
        int maxElement = *max_element(nums.begin(), nums.end());
        if (maxElement > target) return false;
        vector<vector<int>> dp(len, vector<int>(target + 1, 0));
        for (int i = 0; i < len; ++i)
            dp[i][0] = true;
        dp[0][nums[0]] = true;
        for (int i = 1; i < len; ++i)
        {
            int temp = nums[i];
            for (int j = 1; j <= target; ++j)
                if (temp <= j)
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - temp];
                else
                    dp[i][j] = dp[i - 1][j];
        }
        return dp[len - 1][target];
    }
};

// 空间优化
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int len = nums.size();
        if (len < 2) return false;
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum & 1) return false;
        int target = sum / 2;
        int maxElement = *max_element(nums.begin(), nums.end());
        if (maxElement > target) return false;
        vector<int> dp(target + 1, 0);
        dp[0] = true;
        for (int i = 0; i < len; ++i)
        {
            int temp = nums[i];
            for (int j = target; j >= temp; --j)
                dp[j] = dp[j] | dp[j - temp];
        }
        return dp[target];
    }
};

image-20251019214518609

三：不同路径

image-20251019214600877

1. 动态规划

使用二维数组来存储每个位置的步数，当前位置的步数等于上一行和左边位置的和

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
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n));
        for (int i = 0; i < m; ++i) dp[i][0] = 1;
        for (int i = 0; i < n; ++i) dp[0][i] = 1;
        for (int i = 1; i < m; ++i)
            for (int j = 1; j < n; ++j)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        return dp[m - 1][n - 1];
    }
};

// 空间优化
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> dp(n);
        dp[0] = 1;
        for (int i = 0; i < m; ++i)
            for (int j = 1; j < n; ++j)
                dp[j] = dp[j] + dp[j - 1];
        return dp[n - 1];
    }
};

image-20251019214622208

2. 组合数学

对于一个m∗nm*n的二维数组，本质上有m−1m-1次向下移动和n−1n-1次向右移动，因此属于排列组合

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int uniquePaths(int m, int n) {
        long long result = 1;
        for (int x = n, y = 1; y < m; ++x, ++y)
            result = result * x / y;
        return static_cast<int>(result);
    }
};

image-20251019214636662

四：最小路径和

image-20251019214703738

1. 动态规划

该题与上题类似，不过每个元素的值可能不相等，但当前点只能由上和左两个位置得到，选用其中一个最小值和自身值相加即可得到当前点的最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n));
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; ++i) dp[i][0] = dp[i - 1][0] + grid[i][0];
        for (int i = 1; i < n; ++i) dp[0][i] = dp[0][i - 1] + grid[0][i];
        for (int i = 1; i < m; ++i)
            for (int j = 1; j < n; ++j)
                dp[i][j] = min(dp[i - 1][j] , dp[i][j - 1]) + grid[i][j];
        return dp[m - 1][n - 1];
    }
};

image-20251019214812099

五：最长回文子串

image-20251019214838931

1. 动态规划

假设每个字符都为一个回文，对于一个从x到y的字符串，其是否为回文依赖于x+1x+1和y−1y-1是否为字符串，同时需要处理长度为2和为3的情况如“aa”，“bab”

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
class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.size();
        vector<vector<int>> dp(len, vector<int>(len));
        if (len < 2) return s;
        for (int i = 0; i < len; ++i) dp[i][i] = true;
        int maxLen = 1;
        int begin = 0;
        for (int l = 2; l <= len; ++l)
        {
            for (int i = 0; i < len; ++i)
            {
                int right = l + i - 1;
                if (right >= len) break;
                if (s[i] != s[right]) dp[i][right] = false;
                else
                {
                    if (right - i < 3) dp[i][right] = true;
                    else
                    {
                        dp[i][right] = dp[i + 1][right - 1];
                    } 
                }
                if (dp[i][right] && right - i + 1 > maxLen)
                {
                    maxLen = right - i + 1;
                    begin = i;
                }
            }
        }
        return s.substr(begin, maxLen);
    }
};

image-20251019214900587

2. 中心扩展算法

我们以每个字符或者每两个字符为中心然后左右不断扩展，同时用起始位置来维护最大的长度

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
class Solution {
public:
    int len;
    string longestPalindrome(string s) {
        len = s.size();
        int begin = 0;
        int end = 0;
        for (int i = 0; i < len; ++i)
        {
            auto [left1, right1] = Expand(s, i, i);
            auto [left2, right2] = Expand(s, i, i + 1);
            if (right1 - left1 > end - begin)
            {
                begin = left1;
                end = right1;
            }
            if (right2 - left2 > end - begin)
            {
                begin = left2;
                end = right2;
            }
        }
        return s.substr(begin, end - begin + 1);
    }
    pair<int, int> Expand(string& s, int left, int right)
    {
        while (left >= 0 && right < len && s[left] == s[right])
        {
            --left;
            ++right;
        }
        return {left + 1, right - 1};
    }
};

image-20251019214930598

3. Manacher算法

这个题非常巧妙，利用了回文的对称性，从而大量降低了重复的计算

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
    string longestPalindrome(string s) {
        int begin = 0;
        int end = -1;       // 取-1为了下面正确的判断，从而使单个字符能够满足条件
        string temp = "#";
        for (auto& ch : s)
        {
            temp += ch;
            temp += '#';
        }
        s = temp;
        int len = s.size();
        vector<int> arm;
        int right = -1, cur = -1;
        for (int i = 0; i < len; ++i)
        {
            int curArm;
            if (right >= i)
            {
                int isysm = 2 * cur - i;
                int minArm = min(arm[isysm], right - i);
                curArm = Expand(s, i - minArm, i + minArm); 
            } else
            {
                curArm = Expand(s, i, i);
            }
            arm.emplace_back(curArm);
            if (i + curArm > right)
            {
                cur = i;
                right = i + curArm;
            }
            if (curArm * 2 + 1 > end - begin)
            {
                begin = i - curArm;
                end = i + curArm;
            }
        }
        string result;
        for (int i = begin; i <= end; ++i)
            if (s[i] != '#') result += s[i];
        return result;
    }
    int Expand(string& s, int left, int right)
    {
        while (left >= 0 && right < s.size() && s[left] == s[right])
        {
            --left;
            ++right;
        }
        return (right - left - 2)  >> 1;
    }
};

image-20251019214950172