LCR089-LCR094单序列问题

剑指offer（专项突破版）14.2 单序列问题

LCR089.打家劫舍

分析

小偷一次只能进入一幢房屋内盗窃，因此到街道上所有房屋中盗窃需要多个步骤，每一步到一幢房屋内盗窃。由于这条街道有报警系统，因此他每到一幢房屋前都面临一个选择，考虑是不是能进去偷东西。完成一件事情需要多个步骤，并且每一步都面临多个选择，这看起来是一个适合运用回溯法的问题。但由于这个问题并没有要求列举出小偷所有满足条件的偷盗的方法，而只是求最多能偷取的财物的数量，也就是求问题的最优解，因此这个问题适合运用动态规划。

小偷在标号为i的房屋前有两个选择。一个选择是他进去偷东西。由于街道上有报警系统，因此他不能进入相邻的标号为i-1的房屋内偷东西，之前他最多能偷取的财物的最大值是f（i-2）。因此，小偷如果进入标号为i的房屋并盗窃，他最多能偷得f（i-2）+nums[i]（nums是表示房屋内财物数量的数组）。另一个选择是小偷不进入标号为i的房屋，那么他可以进入标号为i-1的房屋内偷东西，因此此时他最多能偷取的财物的数量为f（i-1）。那么小偷在到达标号为i的房屋时他能偷取的财物的最大值就是两个选项的最大值，即$f（i）=max（f（i-2）+nums[i]，f（i-1））$，这就是解决这个问题的状态转移方程。

上述状态转移方程有一个隐含条件，假设i大于或等于2。当i等于0时，f（0）是街道上只有标号为0的一幢房屋时小偷最多能偷得的财物的数量，此时他无所顾忌，直接进入标号为0的房屋偷东西，因此f（1）=nums[0]；当i等于1时，f（1）是街道上只有标号为0和1的两幢房屋时小偷最多能偷得的财物的数量，因为街道上有报警系统，他只能到两幢房屋的其中一幢去偷东西，所以他应该选择到财物数量更多的房屋去偷东西，即f（1）=max（nums[0]，nums[1]）。

带缓存的递归代码

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, -1); // 创建一个大小为n的dp数组，初始值为-1，用于存储子问题的最优解
        return max(helper(nums, dp, n-1), helper(nums, dp, n-2)); // 返回从第0间房子到第n-1间房子中抢劫能获得的最大金额
    }
    
    // 辅助函数，用于计算从第0间房子到第i间房子中能抢劫的最大金额
    int helper(vector<int>& nums, vector<int>& dp, int i) {
        if (i < 0) { // 如果房子索引小于0，返回0（递归基础情况）
            return 0;
        }
        if (dp[i] >= 0) { // 如果dp[i]已经计算过，直接返回其值（记忆化递归）
            return dp[i];
        }
        
        // 递归计算当前房子能抢到的最大金额，分别考虑抢和不抢两种情况
        int result = max(helper(nums, dp, i-1), helper(nums, dp, i-2) + nums[i]);
        dp[i] = result; // 将计算得到的最大金额保存到dp数组中
        return result; // 返回当前房子能抢到的最大金额
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(n)

空间复杂度为O（n）的迭代代码

先求出f（0）和f（1）的值，然后用f（0）和f（1）的值求出f（2），用f（1）和f（2）的值求出f（3），以此类推，直至求出f（n-1）。这种自下而上的思路通常可以用一个for循环实现。

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 1){
            return nums[0];
        }
        vector<int> dp(n);
        dp[0] = nums[0];
        dp[1] = max(nums[1], nums[0]);
        for(int i = 2; i < n; i++){
            dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
        }
        return dp[n-1];
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(n)

空间复杂度为O（1）的迭代代码

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 1){
            return nums[0];
        }
        vector<int> dp(2);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for(int i = 2; i < n; i++){
            dp[i % 2] = max(dp[(i-2)%2]+nums[i], dp[(i-1)%2]);
        }
        return max(dp[0], dp[1]);
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)

用两个状态转移方程分析解决问题

由于小偷到达标号为i的房屋时有两个选择，他可以选择进去偷东西或不进去偷东西，因此可以定义两个表达式f（i）和g（i），其中f（i）表示小偷选择不进入标号为i的房屋偷东西时能偷得的最多财物数量，而g（i）表示小偷选择进入标号为i的房屋偷东西时能偷得的最多财物数量。f（n-1）和g（n-1）的最大值就是小偷能从n幢房屋内偷得的财物的最大值。

接下来尝试找出f（i）和g（i）的状态转移方程。当小偷选择不进入标号为i的房屋偷东西时，那么他不管是不是进入标号为i-1的房屋偷东西都不会触发报警系统，此时他能偷得的财物数量取决于他从标号为0的房屋开始到标号为i-1的房屋为止能偷得的财物数量，因此f（i）=max（f（i-1），g（i-1））。当小偷选择进入标号为i的房屋偷取价值为nums[i]的财物时，那么他一定不能进入标号为i-1的房屋偷东西，否则就会触发报警系统，因此g（i）=f（i-1）+nums[i-1]。

这两个状态转移方程有一个隐含条件，要求i大于0，否则i-1没有意义。当i等于0时，f（0）表示街道上只有标号为0的房屋并且小偷选择不进去偷东西，那么他什么也没有偷到，因此f（0）=0。g（0）表示当只有标号为0的房屋并且小偷选择进去偷东西，那么房屋内财物的价值就是小偷能偷取的东西的价值，即g（0）=nums[0]。

由于需要同时计算f（i）和g（i）的值，因此需要两个一维数组。可以将两个一维数组看成一个表格，f（i）是表格的第1行，g（i）是表格的第2行。可以从左到右随着i的递增填满整个表格。首先f（0）初始化为0，g（0）初始化为标号为0的房屋的财物数量，即2。接着由状态转移方程f（1）=max（f（0），g（0））得出f（1）的值为2，由g（1）=f（0）+nums[1]得出g（1）的值为3。表格内其他的值可以以此类推。

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 1){
            return nums[0];
        }
        vector<vector<int>> dp(2, vector<int>(2));
        // 初始化
        dp[0][0] = 0;
        dp[1][0] = nums[0];
        for(int i = 1; i < n; i++){
            dp[0][i%2] = max(dp[0][(i-1)%2], dp[1][(i-1)%2]);
            dp[1][i%2] = max(dp[0][(i-1)%2]+nums[i], dp[1][(i-1)%2]);
        }
        return max(dp[0][(n-1)%2], dp[1][(n-1)%2]);
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)

LCR090.环形房屋偷盗

分析

由于这个问题和面试题89的区别在于小偷不能同时到标号为0和n-1的两幢房屋内偷东西。如果他考虑去标号为0的房屋，那么他一定不能去标号为n-1的房屋；如果他考虑去标号为n-1的房屋，那么他一定不能去标号为0的房屋。因此，可以将这个问题分解成两个子问题：一个问题是求小偷从标号为0开始到标号为n-2结束的房屋内能偷得的最多财物数量，另一个问题是求小偷从标号为1开始到标号为n-1结束的房屋内能偷得的最多财物数量。小偷从标号为0开始到标号为n-1结束的房屋内能偷得的最多财物数量是这两个子问题的解的最大值。

class Solution {
public:
    // 计算能够偷窃的最大金额
    int rob(vector<int>& nums) {
        int n = nums.size();
        // 如果只有一个房屋，则偷窃该房屋
        if (n == 1) {
            return nums[0];
        }
        // 计算偷窃第一个房屋到倒数第二个房屋时能够偷窃的最大金额
        int res1 = helper(nums, 0, n - 2);        
        // 计算偷窃第二个房屋到最后一个房屋时能够偷窃的最大金额
        int res2 = helper(nums, 1, n - 1);    
        // 返回两种情况下的最大金额
        return max(res1, res2);
    }
    
    // 辅助函数，计算从索引start到end之间能够偷窃的最大金额
    int helper(vector<int>& nums, int start, int end) {
        // 如果只有一个房屋，则返回该房屋的金额
        if (start == end) {
            return nums[start];
        }       
        // 初始化dp数组，用于存储当前房屋能够偷窃的最大金额
        vector<int> dp(2);
        dp[start % 2] = nums[start]; // 如果只偷窃第一个房屋
        dp[(start + 1) % 2] = max(nums[start], nums[start + 1]); // 如果偷窃第一个或第二个房屋        
        // 遍历剩余的房屋，计算能够偷窃的最大金额
        for (int i = start + 2; i <= end; i++) {
            dp[i % 2] = max(dp[(i - 1) % 2], dp[(i - 2) % 2] + nums[i]);
        }        
        // 返回start到end之间能够偷窃的最大金额
        return max(dp[0], dp[1]);
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)

LCR091.粉刷房子

分析

用动态规划解决问题的关键在于找出状态转移方程。根据粉刷的规则，相邻的两幢房子不能被粉刷成相同的颜色，要计算粉刷到标号为i的房子时的成本，还需要考虑标号为i-1的房子的颜色。因此，需要3个表达式，即r（i）、g（i）、b（i），分别表示将标号为i的房子粉刷成红色、绿色和蓝色时粉刷标号从0到i的i+1幢房子的最少成本。假设粉刷每幢房子的成本用一个二维数组costs表示，那么costs[i]中包含的3个数字分别是将标号为i的房子粉刷成红色、绿色和蓝色的成本。当标号为i的房子被粉刷成红色时，标号为i-1的房子可以被粉刷成绿色或蓝色，因此r（i）=min（g（i-1），b（i-1））+costs[i][0]。类似地，当标号为i的房子被粉刷成绿色时，标号为i-1的房子可以被粉刷成红色或蓝色，因此g（i）=min（r（i-1），b（i-1））+costs[i][1]；当标号为i的房子被粉刷成蓝色时，标号为i-1的房子可以被粉刷成红色或绿色，因此b（i）=min（r（i-1），g（i-1））+costs[i][2]。

这3个状态转移方程有一个隐含条件，要求i大于0，否则i-1没有意义。当i等于时，r（0）就是将标号为0的房子粉刷成红色的成本costs[0][0]，g（0）就是将标号为0的房子粉刷成绿色的成本costs[0][1]，而b（0）就是将标号为0的房子粉刷成蓝色的成本costs[0][2]。

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int n = costs.size();
        if(n == 1){
            int res = min(costs[0][0], costs[0][1]);
            res = min(costs[0][2], res);
            return res;
        }
        vector<vector<int>> dp(3, vector<int>(2));  // 三行表示r,g,b
        // 初始化
        dp[0][0] = costs[0][0];
        dp[1][0] = costs[0][1];
        dp[2][0] = costs[0][2];
        // 循环
        for(int i = 1; i < n; i++){
            dp[0][i%2] = min(dp[1][(i-1)%2], dp[2][(i-1)%2]) + costs[i][0];
            dp[1][i%2] = min(dp[0][(i-1)%2], dp[2][(i-1)%2]) + costs[i][1];
            dp[2][i%2] = min(dp[0][(i-1)%2], dp[1][(i-1)%2]) + costs[i][2];
        }
        // 最终结果
        int res = min(dp[0][(n-1)%2], dp[1][(n-1)%2]);
        res = min(dp[2][(n-1)%2], res);
        return res;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)

LCR092.将字符翻转到单调递增

分析

如果前i个字符在翻转某些’0’和’1’之后得到的符合要求的字符串的最后一个字符是’0’，那么无论下标为i的字符是’0’还是’1’，这i+1个字符组成的字符串都是符合要求的。如果前i个字符在翻转某些’0’和’1’之后得到的符合要求的字符串的最后一个字符是’1’，那么必须保证下标为i的字符是’1’，这样才能确保这i+1个字符组成的字符串是符合要求的。

由于翻转下标为i的字符依赖于前i个字符翻转之后最后一个字符是’0’还是’1’，因此要分为两种情况讨论。假设函数f（i）表示把字符串中从下标为0的字符到下标为i的字符（记为S[0..i]，字符串中前i+1个字符组成的子字符串）变成符合要求的字符串并且最后一个字符是’0’所需要的最少翻转次数。假设函数g（i）表示把字符串中S[0..i]变成符合要求的字符串并且最后一个字符是’1’所需要的最少翻转次数。如果字符串的长度是n，那么f（n-1）和g（n-1）就是翻转整个字符串使字符串符合要求并且最后一个字符分别变成’0’和’1’的最少翻转次数，它们的最小值就是整个问题的解。

如果翻转之后下标为i的字符是’0’，那么下标为i-1的字符一定是’0’，否则就不满足所有的字符’0’位于’1’的前面的这个要求。当输入字符串中下标为i的字符（即S[i]）是’0’时，这一步不需要翻转，f（i）=f（i-1）；当输入字符串中下标为i的字符是’1’时，f（i）=f（i-1）+1，因为要把下标为i的字符翻转成’0’。

如果翻转之后下标为i的字符是’1’，那么无论下标为i-1的字符是’0’还是’1’都满足题目的要求。当输入字符串S[i]是’0’时，g（i）=min[f（i-1），g（i-1）]+1，因为要把第i个字符翻转成’1’；当S[i]是’1’时，此时不需要翻转字符，因此g（i）=min[f（i-1），g（i-1）]。

当i等于0时，f（0）和g（0）的值取决于下标为0的字符S[0]。如果S[0]为’0’，那么f（0）的值为0；如果S[0]为’1’，那么f（0）的值为1。g（0）则反之，如果S[0]为’0’，那么g（0）的值为1；如果S[0]为’1’，那么g（0）的值为0。

class Solution {
public:
    int minFlipsMonoIncr(string s) {
        int n = s.length();
        if(n == 1){
            return 0;
        }
        vector<vector<int>> dp(2, vector<int>(2));  // 行代表f和g，列代表i
        // 初始化
        if(s[0] == '0'){
            dp[0][0] = 0;   // 不翻转
            dp[1][0] = 1;   // 翻转   
        }
        else{
            dp[0][0] = 1;   // 翻转
            dp[1][0] = 0;   // 不翻转
        }
        // 遍历
        for(int i = 1; i < n; i++){
            if(s[i] == '0'){
                dp[0][i%2] = dp[0][(i-1)%2];    // 更新f
                dp[1][i%2] = min(dp[0][(i-1)%2], dp[1][(i-1)%2]) + 1;   // 更新g
            }
            else{
                dp[0][i%2] = dp[0][(i-1)%2] + 1;
                dp[1][i%2] = min(dp[0][(i-1)%2], dp[1][(i-1)%2]);
            }
        }
        // 返回结果
        return min(dp[0][(n-1)%2], dp[1][(n-1)%2]);
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)

LCR093.最长的斐波那契数列子序列的长度

分析

由于以A[i]为结尾的斐波那契数列的长度依赖于它前一个数字A[j]，不同的A[j]能和A[i]形成不同的斐波那契数列，它们的长度也可能不同。因此，状态转移方程有两个参数i和j，f（i，j）表示以A[i]为最后一个数字、A[j]为倒数第2个数字的斐波那契数列的长度。如果数组中存在一个数字k，使A[i]=A[j]+A[k]（0≤k＜j＜i），那么f（i，j）=f（j，k）+1，即在以A[j]为最后一个数字、A[k]为倒数第2个数字的斐波那契数列的基础上增加一个数字A[i]，形成更长的一个数列。f（i，j）的值可能是2，此时虽然A[i]和A[j]这两个数字现在还不能形成一个有效的斐波那契数列，但可能会在之后增加一个新的数字使之形成长度为3甚至更长的斐波那契数列。

由于状态转移方程有两个参数i和j，因此需要一个二维数组来缓存f（i，j）的计算结果。i对应二维数组的行号，j对应二维数组的列号。由于i大于j，因此实际上只用到了二维数组的左下角部分。如果数组的长度是n，那么i的取值范围为1～n-1，而j的取值范围为0～n-2。

因为需要查询 A[k] = A[i] - A[j] 是否存在，并且需要得到下标 k，所以需要一个哈希表将数组内所有的数字和下标保存下来供查询。

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n = arr.size();
        vector<vector<int>> dp(n, vector<int>(n));
        unordered_map<int, int> mp;
        // 建立哈希表
        for(int i = 0; i < n; i++){
            mp[arr[i]] = i;
        }
        // 动态规划表
        int res = 0;
        for(int i = 1; i < n; i++){
            for(int j = 0; j < n-1; j++){
                int temp = arr[i] - arr[j];
                // 存在k使得A[i] = A[j] + A[k]
                if(mp.count(temp) && mp[temp] < j){
                    dp[i][j] = dp[j][mp[temp]] + 1;
                }
                else{
                    dp[i][j] = 2;
                }
                res = max(res, dp[i][j]);
            }            
        }
        return res > 2 ? res : 0;
    }
};

• 时间复杂度：上述代码用到了二重循环，因此时间复杂度是$O(n^2)$。
• 空间复杂度由于使用了一个大小为$O(n^2)$的二维数组和一个大小为O(n)的哈希表，因此空间复杂度也是$O(n^2)$。

LCR094.分割回文串

分析

应用动态规划解决问题的关键在于找出状态转移方程。假设字符串为S，下标为i的字符为S[i]，下标从j到i的子字符串为S[j..i]。用f（i）表示从下标为0到i的子字符串S[0..i]的符合条件的最少分割次数。如果字符串的长度是n，那么f（n-1）就是问题的解。

如果子字符串S[0..i]本身就是一个回文，那么不需要分割就符合要求，此时f（i）等于0。如果子字符串S[0..i]不是一个回文，那么对每个下标j（1≤j≤i）逐一判断子字符串S[j..i]是不是回文。如果是回文，那么这就是一个有效的分割方法，此时的分割次数相当于子字符串S[0..j-1]的分割次数再加1，因为这是将子字符串S[0..j-1]按照要求分割之后再在S[j-1]和S[j]这两个字符中间再分割一次。因此，f（i）就是所有符合条件的j对应的f（j-1）的最小值加1。

class Solution {
public:
    int minCut(string s) {
        // 确定回文
        int n = s.length();  // 字符串的长度
        vector<vector<int>> isPalindrome(n, vector<int>(n));  // 二维数组用于记录从第i到第j个字符是否为回文
        for(int i = 0; i < n; i++){  // 遍历字符串s的每个字符
            for(int j = 0; j <= i; j++){  // j从0到i遍历，检查s[j]到s[i]是否为回文串
                if(s[i] == s[j] && (i <= j+1 || isPalindrome[j+1][i-1])){
                    // 如果s[i]等于s[j]，并且s[j+1]到s[i-1]也是回文，则s[j]到s[i]是回文串
                    isPalindrome[j][i] = true;
                }
            }
        }
        // 动态规划
        vector<int> dp(n, 0);  // dp数组，dp[i]表示s[0]到s[i]的最小切割次数
        for(int i = 0; i < n; i++){  // 遍历每个字符
            // 如果s[0]到s[i]本身就是回文串，无需切割
            if(isPalindrome[0][i]){
                dp[i] = 0;
            }
            else{
                // 如果不是回文串，则初始化dp[i]为最大可能切割次数，即i
                dp[i] = i;
                for(int j = 1; j <= i; j++){  // j从1到i遍历
                    if(isPalindrome[j][i]){
                        // 如果s[j]到s[i]是回文串，则更新dp[i]为dp[j-1] + 1的最小值
                        dp[i] = min(dp[i], dp[j-1] + 1);
                    }                    
                }
            }
        }
        return dp[n-1];  // 返回s[0]到s[n-1]的最小切割次数
    }
};

• 时间复杂度：代码需要两个二重循环，第1个二重循环做预处理是为了判断每个子字符串是不是回文。长度为n的子字符串有$O(n^2)$个子字符串，因此至少需要$O(n^2)$的时间才能判断所有的子字符串是不是回文。第2个二重循环是为了计算状态转移方程，时间复杂度也是$O(n^2)$。因此，上述解法的总体时间复杂度是$O(n^2)$。
• 空间复杂度：上述代码使用了两个数组，一个是大小为$O(n^2)$的二维数组，另一个是大小为O（n）的一维数组dp，因此总的空间复杂度是$O(n^2)$。

总结

单序列问题是与动态规划相关的问题中最有可能在算法面试中遇到的题型。这类题目都有适合运用动态规划的问题的特点，如解决问题需要若干步骤，并且每个步骤都面临若干选择，需要计算解的数目或最优解。除此之外，这类题目的输入通常是一个序列，如一个一维数组或字符串。

应用动态规划解决单序列问题的关键是每一步在序列中增加一个元素，根据题目的特点找出该元素对应的最优解（或解的数目）和前面若干元素（通常是一个或两个）的最优解（或解的数目）的关系，并以此找出相应的状态转移方程。一旦找出了状态转移方程，只要注意避免不必要的重复计算，问题就能迎刃而解。