剑指offer一刷：动态规划

剑指 Offer 10- I. 斐波那契数列

难度：简单

方法一：递归法

• 原理：把 f(n) 问题的计算拆分成 f(n-1) 和 f(n-2) 两个子问题的计算，并递归，以 f(0) 和 f(1) 为终止条件。
• 缺点：大量重复的递归计算，例如 f(n) 和 f(n - 1) 两者向下递归需要 各自计算 f(n - 2) 的值。

时间复杂度：O(2^N)，空间复杂度：O(N)。

方法二：记忆化递归法

• 原理：在递归法的基础上，新建一个长度为 n 的数组，用于在递归时存储 f(0) 至 f(n) 的数字值，重复遇到某数字则直接从数组取用，避免了重复的递归计算。
• 缺点：记忆化存储需要使用 O(N) 的额外空间。

时间复杂度：O(N)，空间复杂度：O(N)。

方法三：动态规划

• 原理：以斐波那契数列性质 f(n + 1) = f(n) + f(n - 1) 为转移方程。
• 从计算效率、空间复杂度上看，动态规划是本题的最佳解法。

空间复杂度降低：

若新建长度为 n 的 dp 列表，则空间复杂度为 O(N)。

• 由于 dp 列表第 i 项只与第 i-1 和第 i-2 项有关，因此只需要初始化三个整形变量 sum, a, b，利用辅助变量 sum 使 a, b 两数字交替前进即可（具体实现见代码）。
• 节省了 dp 列表空间，因此空间复杂度降至 O(1)。

class Solution {
    public int fib(int n) {
        int a = 0, b = 1, sum;
        for(int i = 0; i < n; i++){
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;
    }
}

作者：Krahets
链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm/50fji7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O(N)，空间复杂度：O(1)。

剑指 Offer 10- II. 青蛙跳台阶问题

难度：简单

本题可转化为求斐波那契数列第 n 项的值。与上一题完全等价，三个方法不再赘述。

唯一的不同在于起始数字不同：

• 青蛙跳台阶问题： f(0)=1, f(1)=1, f(2)=2；
• 斐波那契数列问题： f(0)=0, f(1)=1, f(2)=1。

class Solution {
    public int numWays(int n) {
        int a = 1, b = 1, sum;
        for(int i = 0; i < n; i++){
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;
    }
}

作者：Krahets
链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm/57xs06/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

剑指 Offer 63. 股票的最大利润

难度：中等

方法一：暴力解法

时间复杂度为 O(N²)，不考虑。

方法二：动态规划

• 状态定义：设动态规划列表 dp，dp[i] 代表以 prices[i] 为结尾的子数组的最大利润（以下简称为 前 i 日的最大利润 ）。
• 转移方程：由于题目限定“买卖该股票一次”，因此前 i 日最大利润 dp[i] 等于前 i - 1 日最大利润 dp[i-1] 和第 i 日卖出的最大利润中的最大值。

dp[i] = max(dp[i - 1], prices[i] - min(prices[0 : i]))

前 i 日最大利润 = max(前 (i-1) 日最大利润, 第 i 日价格 - 前 i 日最低价格)

• 初始状态：dp[0] = 0，即首日利润为 0；
• 返回值：dp[n - 1]，其中 n 为 dp 列表长度。

时间复杂度降低：

前 i 日的最低价格 min(prices[0 : i]) 时间复杂度为 O(i)。而在遍历 prices 时，可以借助一个变量（记为成本 cost）每日更新最低价格。优化后的转移方程为：

dp[i] = max(dp[i?1], prices[i] ? min(cost, prices[i])

空间复杂度降低：

由于 dp[i] 只与 dp[i - 1], prices[i], cost 相关，因此可使用一个变量（记为利润 profit）代替 dp 列表。优化后的转移方程为：

profit = max(profit, prices[i] ? min(cost, prices[i])

class Solution {
    public int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE, profit = 0;
        for(int price : prices) {
            cost = Math.min(cost, price);
            profit = Math.max(profit, price - cost);
        }
        return profit;
    }
}

作者：Krahets
链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm/58vmds/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O(N)，空间复杂度：O(1)。

剑指 Offer 42. 连续子数组的最大和

难度：简单

方法一：动态规划

本题动态规划解法最优，只写动态规划的解法。

• 状态定义：设动态规划列表 dp，dp[i] 代表以元素 nums[i] 为结尾的连续子数组最大和。
• 为何定义最大和 dp[i] 中必须包含元素 nums[i]：保证 dp[i] 递推到 dp[i+1] 的正确性；如果不包含 nums[i]，递推时则不满足题目的连续子数组要求。
• 转移方程：若 dp[i?1]≤0，说明 dp[i?1] 对 dp[i] 产生负贡献，即 dp[i-1] + nums[i] 还不如 nums[i] 本身大。

• 初始状态：dp[0] = nums[0]，即以 nums[0] 结尾的连续子数组最大和为 nums[0]。
• 返回值：返回 dp 列表中的最大值，代表全局最大值。

class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        for(int i = 1; i < nums.length; i++) {
            nums[i] += Math.max(nums[i - 1], 0);
            res = Math.max(res, nums[i]);
        }
        return res;
    }
}

作者：Krahets
链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm/59h9mr/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O(N)，空间复杂度：O(1)。

剑指 Offer 47. 礼物的最大价值

难度：中等

方法一：动态规划

根据题目说明，易得某单元格只可能从上边单元格或左边单元格到达。

设 f(i, j) 为从棋盘左上角走至单元格 (i, j) 的礼物最大累计价值，易得到以下递推关系：f(i, j) 等于 f(i, j-1) 和 f(i-1, j) 中的较大值加上当前单元格礼物价值 grid(i, j)。

因此，可用动态规划解决此问题，以上公式便为转移方程。

可以将原矩阵 $rid$ 用作 $dp$ 矩阵，即直接在 $d$ 上修改，降低空间复杂度。

class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for(int j = 1; j < n; j++) // 初始化第一行
            grid[0][j] += grid[0][j - 1];
        for(int i = 1; i < m; i++) // 初始化第一列
            grid[i][0] += grid[i - 1][0];
        for(int i = 1; i < m; i++)
            for(int j = 1; j < n; j++)
                grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
        return grid[m - 1][n - 1];
    }
}

作者：Krahets
链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm/5vr32s/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O(MN)，空间复杂度：O(1)。

剑指 Offer 46. 把数字翻译成字符串

难度：中等

• 状态定义：设动态规划列表 dp，dp[i] 代表以 x_i 为结尾的数字的翻译方案数量。
• 转移方程：若 x_i 和 x_i-1 组成的两位数字可被整体翻译，则 dp[i] = dp[i - 1] + dp[i - 2]，否则 dp[i] = dp[i - 1]。

注：当 x_i-1 = 0 时，组成的两位数无法被整体翻译（例如 00, 01, 02, ?），大于 25 的两位数也无法被整体翻译（例如 26, 27, ?），因此区间为 [10, 25]。

• 初始状态：dp[0] = dp[1] = 1，即“无数字”和“第 1 位数字”的翻译方法数量均为 1；
• 返回值：dp[n]，即此数字的翻译方案数量；

Q：无数字情况 dp[0] = 1 从何而来？
A：当 num 第 1, 2 位的组成的数字 ∈ [10, 25] 时，显然应有 2 种翻译方法，即 dp[2] = dp[1] + dp[0] = 2，而显然 dp[1] = 1，因此推出 dp[0] = 1。

方法一：字符串遍历

class Solution {
    public int translateNum(int num) {
        String s = String.valueOf(num);
        int a = 1, b = 1;
        for(int i = 2; i <= s.length(); i++) {
            String tmp = s.substring(i - 2, i);
            int c = tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0 ? a + b : a;
            b = a;
            a = c;
        }
        return a;
    }
}

作者：Krahets
链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm/99dnh6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O(N)，空间复杂度：O(N)。

方法二：数字求余

class Solution {
    public int translateNum(int num) {
        int a = 1, b = 1, x, y = num % 10;
        while(num > 9) {
            num /= 10;
            x = num % 10;
            int tmp = 10 * x + y;
            int c = (tmp >= 10 && tmp <= 25) ? a + b : a;
            b = a;
            a = c;
            y = x;
        }
        return a;
    }
}

作者：Krahets
链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm/99dnh6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O(N)，空间复杂度：O(1)。

剑指 Offer 48. 最长不含重复字符的子字符串

难度：中等

• 状态定义：设动态规划列表 dp，dp[j] 代表以字符 s[j] 为结尾的 “最长不重复子字符串” 的长度。
• 转移方程：固定右边界 j，设字符 s[j] 左边距离最近的相同字符为 s[i]，即 s[i] = s[j]。

1. 1. 当 i < 0，即 s[j] 左边无相同字符，则 dp[j] = dp[j-1] + 1；
   2. 当 dp[j - 1] < j - i，说明字符 s[i] 在子字符串 dp[j-1] 区间之外，则 dp[j] = dp[j - 1] + 1；
   3. 当 dp[j - 1] ≥ j - i，说明字符 s[i] 在子字符串 dp[j-1] 区间之中，则 dp[j] 的左边界由 s[i] 决定，即 dp[j] = j - i；

??当 i < 0 时，由于 dp[j - 1] ≤ j 恒成立，因而 dp[j - 1] < j - i 恒成立，因此分支 1. 和 2. 可被合并。

• 返回值：max(dp)，即全局的“最长不重复子字符串”的长度。

方法一：动态规划 + 哈希表

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map dic = new HashMap<>();
        int res = 0, tmp = 0, len = s.length();
        for(int j = 0; j < len; j++) {
            int i = dic.getOrDefault(s.charAt(j), -1); // 获取索引 i
            dic.put(s.charAt(j), j); // 更新哈希表
            tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j]
            res = Math.max(res, tmp); // max(dp[j - 1], dp[j])
        }
        return res;
    }
}

作者：Krahets
链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm/5dz9di/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O(N)，空间复杂度：O(1)。

（字符的 ASCII 码范围为 0 ~ 127 ，哈希表 dic 最多使用 O(128) = O(1) 大小的额外空间）

方法二：双指针 + 哈希表

与方法一本质等价，不同点在于左边界 i 的定义不同。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map dic = new HashMap<>();
        int i = -1, res = 0, len = s.length();
        for(int j = 0; j < len; j++) {
            if(dic.containsKey(s.charAt(j)))
                i = Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i
            dic.put(s.charAt(j), j); // 哈希表记录
            res = Math.max(res, j - i); // 更新结果
        }
        return res;
    }
}

作者：Krahets
链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm/5dz9di/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O(N)，空间复杂度：O(1)。