当前位置：首页 > article >正文

每日算法一练：剑指offer——动态规划（1）

article 2024/12/28 9:38:06

1. 斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

答案需要取模 1e9+7(1000000007) ，如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

0 <= n <= 100

动态规划解法

1. 问题分析：

斐波那契数列的递推公式是：

f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2) (n >= 2)

根据这个递推公式，我们可以通过动态规划的方式计算第 n 项。

2. 暴力递归的缺点：

暴力递归法将问题拆分为多个子问题，且有大量的重复计算。例如，f(n) 和 f(n-1) 都需要计算 f(n-2)，这样就会重复计算很多次。

3. 动态规划的优势：

动态规划通过逐步构建从 f(0) 到 f(n) 的结果，避免了重复计算。在内存方面，传统的动态规划会使用 O(n) 的空间来存储中间结果，但可以通过优化将空间复杂度降低到 O(1)。

动态规划优化方案：

我们发现，计算 f(n) 只依赖于 f(n-1) 和 f(n-2)，所以不需要保存整个数组。我们只需要使用三个变量，分别保存 f(n-2)、f(n-1) 和当前计算的结果，从而将空间复杂度从 O(n) 降低到 O(1)。

4. 实现细节：

我们使用两个变量 a 和 b 来分别存储 f(n-2) 和 f(n-1)，通过循环计算每个新的 f(n)，并在每次循环中更新这两个变量。

5. 大数越界处理：

在计算斐波那契数列时，数值会随着 n 的增大而变得非常大。为了避免溢出，我们使用了模运算 % 1000000007 来保证结果不会超过整数的范围。这个常数是一个常见的模数，能够有效防止大数越界。

代码实现：

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
            a = b;
            b = sum;
        }
        
        // 返回斐波那契数列的第 n 项
        return a;
    }
}

代码解析：

初始化变量：
- a = 0：表示斐波那契数列的第 0 项。
- b = 1：表示斐波那契数列的第 1 项。
- sum 用来存储当前计算的斐波那契数值。
循环计算：
- 我们使用一个 for 循环从 i = 0 到 i = n-1 计算每一项斐波那契数。每次循环中，通过公式 sum = (a + b) % 1000000007 计算出当前的斐波那契数，并更新 a 和 b。
返回结果：
- 当循环结束时，a 保存的是斐波那契数列的第 n 项，直接返回 a 即可。

时间复杂度和空间复杂度分析：

时间复杂度：
每次循环中的操作都是常数时间复杂度 O(1)，循环的次数为 n，因此总的时间复杂度是 O(n)。
空间复杂度：
只使用了三个变量 a、b 和 sum，因此空间复杂度为 O(1)。

小结：

这个 Java 解法通过动态规划和空间优化，计算了斐波那契数列的第 n 项。与暴力递归相比，避免了重复计算，且通过 O(1) 的空间优化使得解法更加高效。在处理大数越界时，我们使用了模运算，确保返回的结果不会超出整数范围。

2. 跳跃训练

今天的有氧运动训练内容是在一个长条形的平台上跳跃。平台有 num 个小格子，每次可以选择跳 一个格子 或者 两个格子。请返回在训练过程中，学员们共有多少种不同的跳跃方式。

结果可能过大，因此结果需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：2

示例 2：

输入：n = 5
输出：8

提示：

0 <= n <= 100

这道题目是经典的动态规划问题，可以通过斐波那契数列来建模。题目要求计算青蛙跳上 n 级平台的跳法数，跳法的递推公式为：

青蛙跳到第 n 级平台时，最后一步要么跳 1 级平台，要么跳 2 级平台。
如果青蛙最后跳的是 1 级平台，那么剩下 n-1 级平台的跳法数是 f(n-1)。
如果青蛙最后跳的是 2 级平台，那么剩下 n-2 级平台的跳法数是 f(n-2)。

因此，f(n) 可以通过递推公式表示为：

f(n) = f(n-1) + f(n-2)

并且初始条件为：

f(0) = 1（表示青蛙不跳时有 1 种方法，即站在原地）
f(1) = 1（表示青蛙只能跳 1 级）
f(2) = 2（表示青蛙可以跳 1 级两次，或者直接跳 2 级）

动态规划解法

状态定义：定义一个一维数组 dp，其中 dp[i] 代表跳上第 i 级平台的跳法数。
转移方程：根据上面的推导，dp[i] = dp[i-1] + dp[i-2]。
初始状态：
- dp[0] = 1，表示不跳时有 1 种方式。
- dp[1] = 1，表示只能跳 1 级。
返回值：返回 dp[num]，即跳上 num 级平台的跳法数。

空间优化

在动态规划中，dp[i] 只与 dp[i-1] 和 dp[i-2] 有关，因此我们可以用两个变量来保存这两个值，从而优化空间复杂度至 O(1)。

Java 代码实现：

class Solution {
    public int trainWays(int num) {
        // 如果只有 0 或 1 级平台，直接返回 1
        if (num == 0 || num == 1) {
            return 1;
        }

        int a = 1, b = 1, sum;
        
        // 迭代计算跳法数
        for (int i = 2; i <= num; i++) {
            sum = (a + b) % 1000000007;  // 防止大数越界
            a = b;  // 更新 a 为上一轮的 b
            b = sum;  // 更新 b 为当前计算的结果
        }

        return b;  // 返回第 num 级平台的跳法数
    }
}

代码解析：

初始化变量：
- a = 1 和 b = 1 分别代表 dp[0] 和 dp[1]。
- sum 用于存储当前的跳法数。
循环计算跳法数：
- 从 i = 2 开始循环，逐步计算到 num。每次计算时，sum 保存了 dp[i] = dp[i-1] + dp[i-2] 的结果，并对其取模 1000000007，避免溢出。
更新变量：
- a = b 表示 dp[i-2]，为下一次循环准备。
- b = sum 表示 dp[i-1]，更新为当前的跳法数。
返回结果：
- 最终，b 即为第 num 级平台的跳法数。

时间复杂度和空间复杂度分析：

时间复杂度：
计算 f(num) 需要循环 num - 1 次，因此时间复杂度为 O(n)。
空间复杂度：
使用了常数空间来存储 a、b 和 sum，所以空间复杂度为 O(1)。

小结：

通过动态规划方法，我们能够高效地计算出青蛙跳上 n 级平台的跳法数，并通过空间优化将空间复杂度降至 O(1)。同时，通过使用模运算 1000000007，有效地避免了大数越界问题。、

2. 跳跃训练

请设计一个程序来支持用户在文本编辑器中的模糊搜索功能。用户输入内容中可能使用到如下两种通配符：

'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的那一个元素。

请返回用户输入内容 input 所有字符是否可以匹配原文字符串 article。

示例 1:

输入: article = "aa", input = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入: article = "aa", input = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:

输入: article = "ab", input = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

提示：

1 <= article.length <= 20
1 <= input.length <= 20
article 只包含从 a-z 的小写字母。
input 只包含从 a-z 的小写字母，以及字符 . 和 * 。
保证每次出现字符 * 时，前面都匹配到有效的字符

解题思路

给定字符串 s 和正则表达式 p，要求判断 s 是否能通过 p 匹配。

正则表达式中有两种特殊字符：

. 匹配任意单个字符。
* 匹配零个或多个前面的字符（* 总是与它前面的字符一起出现，如 a* 匹配空字符、a、aa 等）。

动态规划解法

我们可以使用动态规划（DP）来解决这个问题，定义一个二维的 dp 数组，其中 dp[i][j] 表示 s 的前 i 个字符与 p 的前 j 个字符是否匹配。

状态定义：

dp[i][j]：表示 s 的前 i 个字符和 p 的前 j 个字符是否能够匹配。

转移方程：

当 p[j - 1] == '*' 时：
- dp[i][j] 可以由以下几种情况推导出来：
  - dp[i][j - 2]：表示 p[j - 1] 和 p[j - 2] 看作匹配零次，即跳过这两个字符。
  - dp[i - 1][j] && s[i - 1] == p[j - 2]：表示 p[j - 2] 重复一次并与 s[i - 1] 匹配。
  - dp[i - 1][j] && p[j - 2] == '.'：表示 p[j - 2] 为 .，可以匹配任何字符，继续与 s[i - 1] 匹配。
当 p[j - 1] != '*' 时：
- dp[i][j] 可以由以下几种情况推导出来：
  - dp[i - 1][j - 1] && s[i - 1] == p[j - 1]：表示当前字符匹配，继续比较 s[i - 1] 和 p[j - 1]。
  - dp[i - 1][j - 1] && p[j - 1] == '.'：表示当前字符是 .，可以匹配任何字符，继续比较 s[i - 1] 和 p[j - 1]。

初始条件：

dp[0][0] = true：两个空字符串能够匹配。
对于 dp[0][j]，只有当 p[j - 1] == '*' 且 p[j - 2] == '*' 时，才能匹配（即 p 的奇数位必须是 *，这样 p 才可以为空）。

最终结果：

返回 dp[m - 1][n - 1]，即 s 和 p 完全匹配与否。

代码实现：

class Solution {
    public boolean articleMatch(String s, String p) {
        int m = s.length() + 1, n = p.length() + 1;
        boolean[][] dp = new boolean[m][n];
        dp[0][0] = true;
        
        // 初始化 dp[0][j]（处理 p 开头为 * 的情况）
        for (int j = 2; j < n; j += 2)
            dp[0][j] = dp[0][j - 2] && p.charAt(j - 1) == '*';
        
        // 状态转移
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (p.charAt(j - 1) == '*') {
                    // 如果 p[j-1] 是 '*'，有三种情况：
                    if (dp[i][j - 2]) dp[i][j] = true; // p[j-1] 作为 0 次匹配
                    else if (dp[i - 1][j] && s.charAt(i - 1) == p.charAt(j - 2)) dp[i][j] = true; // p[j-2] 作为 1 次匹配
                    else if (dp[i - 1][j] && p.charAt(j - 2) == '.') dp[i][j] = true; // p[j-2] 作为任意字符匹配
                } else {
                    // 如果 p[j-1] 不是 '*'，有两种情况：
                    if (dp[i - 1][j - 1] && s.charAt(i - 1) == p.charAt(j - 1)) dp[i][j] = true;  // p[j-1] 和 s[i-1] 匹配
                    else if (dp[i - 1][j - 1] && p.charAt(j - 1) == '.') dp[i][j] = true;         // p[j-1] 为 '.'，匹配任意字符
                }
            }
        }
        
        return dp[m - 1][n - 1];
    }
}

复杂度分析：

时间复杂度：O(MN)，其中 M 和 N 分别为 s 和 p 的长度。需要遍历整个 dp 矩阵来计算结果。
空间复杂度：O(MN)，需要 M * N 的空间来存储 dp 矩阵。

总结：

通过动态规划方法，我们能够有效地解决正则表达式匹配问题，处理了特殊字符 . 和 * 的情况，并且通过状态转移公式实现了高效的匹配判断。

4. 连续天数的最高销售额

某公司每日销售额记于整数数组 sales，请返回所有连续一或多天销售额总和的最大值。

要求实现时间复杂度为 O(n) 的算法。

示例 1:

输入：sales = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：[4,-1,2,1] 此连续四天的销售总额最高，为 6。
示例 2:

输入：sales = [5,4,-1,7,8]
输出：23
解释：[5,4,-1,7,8] 此连续五天的销售总额最高，为 23。
提示：

1 <= arr.length <= 10^5
-100 <= arr[i] <= 100

解题思路：
本题是经典的“最大子数组和”问题，使用动态规划可以高效解决。我们需要在一个数组中找到连续子数组的最大和。通过分析问题，我们可以得到以下的动态规划解决方案。

动态规划分析：

状态定义：定义一个数组 dp[i] 表示以 sales[i] 结尾的连续子数组的最大和。
目标是找到一个最大值 dp[i]，它代表了一个子数组的最大和。
状态转移方程：
- 若 dp[i-1] <= 0，说明前一个子数组的和对当前子数组没有正贡献（可能是负值），因此我们可以选择从 sales[i] 开始一个新的子数组。
- 否则，我们继续累加前一个子数组的和，并加上当前元素 sales[i]。
所以有：
dp[i]=max⁡(dp[i−1]+sales[i],sales[i])dp[i] = \max(dp[i-1] + sales[i], sales[i])
这里的意思是，如果前一个子数组的和小于等于零，那么就从当前元素开始新的一段子数组，否则就累加到之前的子数组和中。
初始状态：初始状态为 dp[0] = sales[0]，即以 sales[0] 结尾的最大子数组和就是 sales[0] 本身。
最终结果：我们的最终目标是找到所有 dp[i] 中的最大值，即：
res=max⁡(dp[0],dp[1],...,dp[n−1])\text{res} = \max(dp[0], dp[1], ..., dp[n-1])

空间优化：

由于 dp[i] 只与 dp[i-1] 和当前元素 sales[i] 有关，因此我们不需要维护一个完整的 dp 数组，可以直接在原数组 sales 上进行修改，以节省空间。具体做法是，直接使用 sales[i] 来更新最大和。

最终代码实现：

class Solution {
    public int maxSales(int[] sales) {
        int res = sales[0];  // 初始化结果为第一个元素
        for (int i = 1; i < sales.length; i++) {
            sales[i] += Math.max(sales[i - 1], 0);  // 如果前一个子数组和为负，则重新从当前元素开始
            res = Math.max(res, sales[i]);  // 更新最大和
        }
        return res;
    }
}