《剑指Offer》第2版：动态规划及记忆化搜索之新视角

《剑指Offer》第2版：动态规划与记忆化搜索的崭新观察

前三个题目属于同一类模型，因此分别采用递推、记忆化以及动态规划的方式进行求解。

一、p74-JZ10 斐波那契数列

斐波那契数列_牛客题霸_牛客网

class Solution {
public:
    int Fibonacci(int n) {
        // 编写代码此处
        if(n == 1 || n == 2) return 1;
        int a = 1, b = 1, c = 1;
        while(n > 2) {
            c = a + b;
            a = b;
            b = c;
            --n;
        }
        return c;
    }
};

二、扩展p77-JZ10青蛙跳台阶

跳台阶_牛客题霸_牛客网

class Solution {
public:
    // 本题采用记忆化搜索方式
    int memory[41] = {0};
    int jumpFloor(int n) {
        if(n <= 2) return n; // 处理n为1或2的情况
        if(memory[n]) return memory[n];
        return memory[n] = jumpFloor(n - 1) + jumpFloor(n - 2);
    }
};

三、扩展p79-JZ10矩阵覆盖

矩形覆盖_牛客题霸_牛客网

class Solution {
public:
    int rectCover(int n) {
        if(n <= 2) return n;
        vector<int> dp(n + 1);
        dp[1] = 1, dp[2] = 2;
        for(int i = 3; i <= n; ++i) dp[i] = dp[i - 1] + dp[i - 2]; // 最后放置竖的或者两个正的
        return dp[n];
    }
};

四、扩展p78-JZ10青蛙跳台阶扩展问题

跳台阶扩展问题_牛客题霸_牛客网

动态规划解法：

class Solution {
public:
    int jumpFloorII(int number) {
        // dp[n]表示跳到n台阶的跳法总数
        // dp[n] = dp[n-1] + dp[n-2] + ... + dp[0]
        // dp[n-1] = dp[n-2] + dp[n-3] + ... + dp[0]
        // 归纳可得dp[n] = 2 * dp[n-1]
        vector<int> dp(number);
        dp[0] = 1;
        for(int i = 1; i < number; ++i) dp[i] = dp[i - 1] * 2;
        return dp[number - 1];
    }
};

递归解法：

class Solution {
public:
    int jumpFloorII(int number) {
        if(number == 1) return 1; // 1阶或0阶都只有1种跳法
        return 2 * jumpFloorII(number - 1); // 递推关系f(n) = 2*f(n-1)
    }
};

数学规律解法：

class Solution {
public:
    int jumpFloorII(int number) {
        if(number == 1) return 1;
        return pow(2, number - 1); // 根据规律f(n)=2^(n-1)直接计算
    }
};

五、p124-JZ19 正则表达式匹配

正则表达式匹配__牛客网

class Solution {
public:
    bool match(string s, string p) {
        // dp[i][j]表示p的前j个字符能否匹配s的前i个字符
        int m = s.size(), n = p.size();
        s = ' ' + s; p = ' ' + p; // 调整下标以便处理
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        dp[0][0] = true; // 空字符串匹配空模式
        // 处理*可以匹配空的情况
        for(int j = 2; j <= n; j += 2) {
            if(p[j] == '*') dp[0][j] = true;
            else break;
        }
        // 动态规划转移
        for(int i = 1; i <= m; ++i) {
            for(int j = 1; j <= n; ++j) {
                if(p[j] == '*') {
                    // *不匹配则看前两个字符，或者匹配一个后看当前模式
                    dp[i][j] = dp[i][j - 2] || ((p[j - 1] == s[i] || p[j - 1] == '.') && dp[i - 1][j]);
                } else {
                    // 当前字符匹配则看前一个状态
                    dp[i][j] = (s[i] == p[j] || p[j] == '.') && dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
};

六、p218-JZ42连续子数组的最大和

连续子数组最大和_牛客题霸_牛客网

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> nums(n), dp(n);
    for(int i = 0; i < n; ++i) cin >> nums[i];
    dp[0] = nums[0];
    for(int i = 1; i < n; ++i) {
        dp[i] = max(dp[i - 1] + nums[i], nums[i]);
    }
    cout << *max_element(dp.begin(), dp.end()) << endl;
    return 0;
}

七、扩展p218-JZ42 连续子数组的最大和（二）

连续子数组的最大和(二)_牛客题霸_牛客网

class Solution {
public:
    vector<int> FindGreatestSumOfSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n);
        dp[0] = nums[0];
        int begin = 0; // 标记当前子数组的起始位置
        int left = 0, right = 0; // 标记最长子数组的区间
        int maxsum = nums[0]; // 记录最大和
        for(int i = 1; i < n; ++i) {
            dp[i] = max(nums[i], dp[i - 1] + nums[i]);
            if(nums[i] + dp[i - 1] < nums[i]) {
                begin = i; // 更新新的起始位置
            }
            // 更新最大和及最长子数组区间
            if(dp[i] > maxsum || (dp[i] == maxsum && (right - left + 1) < (i - begin + 1))) {
                maxsum = dp[i];
                left = begin;
                right = i;
            }
        }
        vector<int> ret;
        ret.reserve(right - left + 1);
        for(int i = left; i <= right; ++i) {
            ret.emplace_back(nums[i]);
        }
        return ret;
    }
};

八、p231-JZ46 把数字翻译成字符串

把数字翻译成字符串_牛客题霸_牛客网

class Solution {
public:
    int solve(string nums) {
        if(nums == "0") return 0;
        int n = nums.size();
        nums = ' ' + nums; // 调整下标
        vector<int> dp(n + 1);
        dp[0] = 1; // 初始状态
        dp[1] = (nums[1] != '0');
        for(int i = 2; i <= n; ++i) {
            if(nums[i] != '0') {
                dp[i] += dp[i - 1];
            }
            int val = (nums[i - 1] - '0') * 10 + nums[i] - '0';
            if(val >= 10 && val <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
};

九、p233-JZ47 礼物的最大价值

礼物的最大价值_牛客题霸_牛客网

动态规划解法：

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

记忆化搜索解法：

class Solution {
public:
    int m, n;
    int maxValue(vector<vector<int>>& nums) {
        m = nums.size(), n = nums[0].size();
        vector<vector<int>> memory(m, vector<int>(n));
        return dfs(nums, m - 1, n - 1, memory);
    }
    int dfs(vector<vector<int>>& nums, int i, int j, vector<vector<int>>& memory) {
        if(i == 0 && j == 0) return nums[0][0]; // 到达起点
        if(memory[i][j]) return memory[i][j];
        if(i == 0) return memory[0][j] = nums[0][j] + dfs(nums, 0, j - 1, memory);
        if(j == 0) return memory[i][0] = nums[i][0] + dfs(nums, i - 1, 0, memory);
        return memory[i][j] = nums[i][j] + max(dfs(nums, i - 1, j, memory), dfs(nums, i, j - 1, memory));
    }
};

十、p312-JZ66 构建乘积数组

构建乘积数组_牛客题霸_牛客网

![](https://i-blog.cs