5.最长回文子串

单独处理长度为1和2的字符串

状态转移：字串加上相同的首尾

1
dp[i][j] = (s[i] == s[j] && dp[i+1][j-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
string longestPalindrome(string s) {
    string ans;
    int n = s.size();
    //初始化二维vector，初始值为0
    vector<vector<int>> dp(n, vector<int>(n));
    //外层循环用的是字串的长度，dp矩阵对角线（i==j）代表字串长度为1，对角线两侧的斜线代表字串长度为2，依次往外扩展更新
    for (int len = 0; len < n; len++)
    {c
        //对于dbabcad，首轮更新d, b, a, b, c, a, d对应的dp; 第二轮更新db, ba, ab, bc, ca, ad对应的dp; 然后是dba, bab, abc......（它根据首轮的更新的dp做s[i] == s[j] && dp[i + 1][j - 1]判断）
        for (int i = 0; i < n - len; i++)
        {
            int j = i + len;
            if (len == 0)
            {
                dp[i][j] = 1;
            }
            else if (len == 1)
            {
                dp[i][j] = s[i] == s[j];
            }
            else
            {
                dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1]);
            }
            //如果找到了更长的字串，更新新的字串
            if (dp[i][j] && len + 1 > ans.size())
            {
                //substr(i, j): 从下标i开始截取j位
                ans = s.substr(i, len + 1);
            }
        }
    }
    return ans;
}

53. 最大子序和

状态转移：nums[i]为当前遍历到的数，比较在已有数组上加上当前数值（数组里加当前数值）和当前数值的大小（开一个新数组）

1
max(f[i-1]+nums[i], nums[i])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int maxSubArray(vector<int>& nums) {
        vector<int> f;
        if(nums.empty())
        {return 0;}
        f.push_back(nums[0]);
        for(int i = 1; i < nums.size(); i++)
        {
            f.push_back(max(f[i-1]+nums[i], nums[i]));
        }
        int compare = f[0];
        for(auto x:f)
        {
            compare = max(x, compare);
        }
        return compare;
    }

超级码力复赛 3.秋叶收藏集

1
2
3
4
5
6
要将叶子调整为“红黄红”排列，r为红，y为黄，每次可将r调整为y，也可将y调整为r，求调整所需最小次数

示例：
输入：leaves = "rrryyyrryyyrr"
输出：2
解释：调整两次，将中间的两片红叶替换成黄叶，得到 "rrryyyyyyyyrr"
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
int minimumOperations(string leaves) {
    int n = leaves.size();
    //cout << "n" <<n << endl;
    int start = 0;
    int end = leaves.size() - 1;

    vector<vector<int>> dp(n - 2, vector<int>(n - 2, 100000));
    int temp = 0;
    if (leaves[0] == 'y')
    {
        temp++;
    }
    if (leaves[1] == 'r')
    {
        temp++;
    }
    for (int i = 2; i < n; i++)
    {
        if (leaves[i] == 'y')
        {
            temp++;
        }
    }
    dp[0][1] = temp;
    int x = 0;
    int y = 2;
    while (x != n - 3)
    {
        while (y != n - 2)
        {
            if (leaves[y] == 'y')
                dp[x][y] = dp[x][y - 1] - 1;
            else
                dp[x][y] = dp[x][y - 1] + 1;
            y++;
        }
        if (x + 2 == n - 2)
            break;
        //cout << "test" << endl;
        if (leaves[x+1] == 'y')
            dp[x + 1][x + 2] = dp[x][x + 2] + 1;
        else
            dp[x + 1][x + 2] = dp[x][x + 2] - 1;
        //cout << "test2" << endl;
        x++;
        y = x + 2;
        //cout << "x y " << x << y << endl;
        /*for (int a = 0; a < dp.size(); a++)
        {
            for (int b = 0; b < dp[0].size(); b++)
            {
                cout << dp[a][b] << " ";
            }
            cout << endl;
        }*/
    }
    int res = dp[0][0];
    for (int a = 0; a < dp.size(); a++)
    {
        for (int b = 0; b < dp[0].size(); b++)
        {
            if (dp[a][b] < res)
            {
                res = dp[a][b];
            }
        }
    }
    // cout << res;
    return res;
}

32. 最长有效括号

寻找转移方程：

每个dp元素代表以该位置为结尾的最长有效括号数，也就是说当以’)’为结尾才可能不为0

当发现s[i]位置以’)’结尾，检查s[i-1]

如果s[i-1] == '('，dp[i] = dp[i-2] + 2

如果s[i-1] == ')'并且 s[i - dp[i-1] - 1] == '(' ，dp[i] = dp[i-1] + dp[i - dp[i-1] - 2] + 2

对第二种情况举例：( ) ( ( ) ( ) )，检测到最后一位为’)’并且倒数第二位也为’)’，这时dp[6] = 4, dp[7] = dp[6]（dp[i-1]） + dp[1]（dp[7 - dp[6] -2]） + 2 = 4 + 2 + 2，分别代表第四个到第七个括号组成的dp[i-1]、第一个和第二个括号组成的dp[i - dp[i-1] - 1]，（加上这个是因为除去dp[i-1]和第三个和第八个配对的括号以外，第一个和第二个括号也因为原本没有配对的第三个括号成功配对而连接起来）、第三个和第八个括号组成的新配对的括号组

47. 礼物的最大价值

构造“矩阵最优路径的寻径问题”的dp矩阵，dp矩阵每个元素的含义是到当前点的最大收益

转移方程：

1
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j];

这样的话就需要填充边界：使dp矩阵的维度加一，填充0

本题的优化：可将dp矩阵维度降为一维，在每一个外层循环中覆盖更新dp

62. 不同路径

转移方程:

1
dp[i][j] = dp[i-1][j]+dp[i][j-1];

动态规划中要下意识地思考是否能够降低空间复杂度

本题中每一行的计算都只需要当前行和上一行的信息，所以将空间复杂度O(n^2^)降至O(2n):

只构造两个一维数组pre和cur，分别保存上一行和当前行的值

每次修改完当前行的值以后，将当前行cur复制给pre

进一步优化空间复杂度至O(n):

只构造一个一维数组cur，对应上面的转移方程：

1
cur[j] += cur[j-1];

因为在更新cur[j]时，更新前的cur[j]即为上一行的j列值，只需在此之上加上cur[j-1]即可

64. 最小路径和

转移方程：

1
2
3
4
5
6
7
8
if(i == 1 || j == 1)
{
	dp[i][j] = i == 1 ? dp[i][j-1] + grid[i-1][j-1] : dp[i-1][j] + grid[i-1][j-1];
}
else
{
	dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1];
}

为了防止下标左溢出，dp矩阵是(m+1) * (n+1)的，第一行和第一列填充0

第一行和第一列做单独处理，因为当前点的值应为左侧和上侧的较小值加上当前点的值，而第一行的点的值只能为左侧的值加上当前点的值，第一列的点的值只能为上侧的点的值加上当前点的值

70. 爬楼梯

转移方程：

1
2
3
4
5
6
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; i++)
{
	dp[i] = dp[i-2] + dp[i-1];
}

防止左溢出，提前设定dp[1]和dp[2]，并设置n=1和n=2时的返回值

72. 编辑距离

问题本质等同于有三种操作：

在单词 A 中插入一个字符，如果horse到ro的编辑距离为a，那么到ros的编辑距离不会超过a+1

在单词 B 中插入一个字符，如果hors到ros的编辑距离为b，那么horse到ros的编辑距离不会超过b+1

修改单词 A 的一个字符，如果hors到ro的编辑距离为c，那么horse到ros的编辑距离不会超过c+1

因此产生状态转移方程：

1
2
int label = word1[i-1] == word2[j-1] ? 0 : 1; //先判断A和B最后一个字母是否相同
dp[i][j] = min(min(dp[i-1][j] + 1, dp[i][j-1] + 1), dp[i-1][j-1] + label);