动态规划

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

题目描述

写一个函数，输入 n，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

1
2

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：1

1
2

示例 2：

输入：n = 5
输出：5

1
2

提示：

0 <= n <= 100

**思路**

标签：动态规划
本题是经典的动态规划问题，围绕斐波那契数列方程 F(n+1) = F(n) + F(n−1)F(n+1)=F(n)+F(n−1) 进行解题，所以在求 n+1 元素时，只需要知道第 n 和 n-1 个元素即可
- 状态定义： F[n] 表示的含义为斐波那契数列中第 n 个数字
- 转移方程： F(n+1) = F(n) + F(n−1)F(n+1)=F(n)+F(n−1) ，所以在求 n+1 元素时，只需要知道第 n 和 n-1 个元素即可，故而运算过程中不需要保存数组
- 初始状态： F[0] = 0, F[1] = 1 ，因为在计算 n+1 时需要 2 个元素，所以要初始化 2 个值；
其中取模 1000000007 运算主要是为了避免数字溢出，这步运算在每次计算出新的斐波那契数时进行即可，因为模运算的特性，后续再进行加法运算也不会有任何影响
模运算特性：(x + y) % z = ((x % z) + (y % z)) % z
时间复杂度：O(n)，空间复杂度：O(1)

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

1
2
3
4
5
6
7
8
9
10
11

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

题目描述

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：2

1
2

示例 2：

输入：n = 7
输出：21

1
2

提示：

0 <= n <= 100
注意：本题与主站 70 题相同

**思路**

标签：动态规划
整体思路：本质是斐波那契数列和循环求余法
- 令 F(n) 表示为上第 n 层台阶时所需要的跳法
- 因为一次可以跳上 1 级台阶，也可以跳上 2 级台阶，所以 F(n 可以从 F(n-1) 跳上来，也可以从 F(n-2) 跳上来
- 推导出 F(n) = F(n-1) + F(n-2)
- 由于第 n 层的跳法数量只取决于 n-1 和 n-2 层，所以存储时，可以仅存储这三个值，优化空间复杂度
- 时间复杂度：O(n)，空间复杂度：O(1)

算法流程

围绕斐波那契数列方程 F(n) = F(n-1) + F(n−2) 进行解题，所以在求 n 元素时，只需要知道第 n-1 和 n-2 个元素即可
- 状态定义： F[n] 表示的含义为斐波那契数列中第 n 个数字
- 转移方程： F(n) = F(n-1) + F(n−2)，运算过程中仅存储这三个数值即可
- 初始状态： F[0] = 1, F[1] = 1，因为在计算 n 时需要 2 个元素，所以要初始化 2 个值；
其中取模 1000000007 运算主要是为了避免数字溢出，这步运算在每次计算出新的斐波那契数时进行即可，因为模运算的特性，后续再进行加法运算也不会有任何影响
- 模运算特性：(x + y) % z = ((x % z) + (y % z)) % z
为什么要对 1000000007 取模
- 1000000007 是一个质数（素数），对质数取模能最大程度避免冲突
- int32 位的最大值为 2147483647，所以对于 int32 位来说 1000000007 足够大

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

1
2
3
4
5
6
7
8
9
10
11

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

题目描述

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为 O(n)。

示例 1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

1
2
3

提示：

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

**思路**

标签：动态规划
整体思路：通过动态规划计算每一步的状态可以在遍历数组结束后得到结果，成为最优解
时间复杂度：O(n)，空间复杂度：O(1)

算法流程

状态定义：动态规划数组为 dp，dp[i] 表示以 nums[i] 结尾的连续子数组最大和
状态转移方程：
- 当 dp[i - 1] > 0 时，则 dp[i] = dp[i-1] + nums[i]，因为此时 dp[i - 1] 产生正向增益，所以要加上去
- 当 dp[i - 1] ≤ 0 时，则 dp[i] = nums[i]，因为此时 dp[i - 1] 产生负向增益，所以不需要添加
初始状态：dp[0] = nums[0]
结果值：dp 数组中的最大值，就是最终的结果
其中为了降低空间复杂度，可以将 dp 数组与 nums 数组合并，避免开辟新的内存空间

class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        for(int i = 1; i < nums.length; i++) {
            
            // 当 dp[i - 1] > 0 时，则 dp[i] = dp[i-1] + nums[i]，因为此时 dp[i - 1] 产生正向增益，所以要加上去
            // 当 dp[i - 1] ≤ 0 时，则 dp[i] = nums[i]，因为此时 dp[i - 1] 产生负向增益，所以不需要添加
            if(nums[i - 1] > 0) {
                nums[i] += nums[i - 1];
            }
            
            // dp 数组中的最大值，就是最终的结果
            res = Math.max(res, nums[i]);
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

题目描述

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 "a" ，1 翻译成 "b"，……，11 翻译成 "l"，……，25 翻译成 "z"。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例 1:

输入：12258
输出：5
解释：12258 有 5 种不同的翻译，分别是 "bccfi","bwfi","bczi","mcfi" 和 "mzi"

1
2
3

**思路**

标签：动态规划
整体思路：
- 翻译方案可能与前两步骤有关，令 dp[n] 表示第 n 个位置方案数量，第 [n] 位与区间 [0:n-1] 位必然可以组成 dp[n-1] 个方案，如果前两位 [n-1:n] 组成的数字在区间 10-26 之间，第 [n-1:n] 位与区间 [0:n-2] 位必然可以组成 dp[n-2]个方案，所以可以根据该思路写出动态规划方程
复杂度：
- 时间复杂度：O(n)。n 代表 num 的数字长度，需要遍历 n 次
- 空间复杂度：O(n)。需要将 num 转为字符串，所以要消耗字符串长度 n 的空间

算法流程

状态定义： dp[n] 表示第 n 个位置方案数量
转移方程：
- 令 [n-1:n] 组成的数字为 x
- dp[n] = dp[n-1] + dp[n-2], x >= 10 && x <= 25
- dp[n] = dp[n-1], x < 10 && x > 25
初始状态：dp[0] = 1，dp[1] = 1
因为该动态规划只需要 n-1 和 n-2 步骤的数据即可，所以可以不使用 dp 数组存储，使用 2 个变量存储数值即可

class Solution {
    public int translateNum(int num) { 
        String strNum = String.valueOf(num);
        int len = strNum.length();
        
        int left = 1;
        int right = 1;
        
		// start from 2, this can guarantee the index is not out of scope 
        for (int i = 2; i <= len; i++) {
            String str = strNum.substring(i - 2, i);
            int sum = str.compareTo("10") >= 0 && str.compareTo("25") <= 0 ? left + right : right;
            left = right;
            right = sum;
        }
        return right;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

题目描述

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

示例 1:

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

1
2
3
4
5
6
7
8

提示：

0 < grid.length <= 200
0 < grid[0].length <= 200

思路

标签：动态规划
整体思路：在遍历二维数组时，通过状态转移方程计算出当前位置的最大价值，同时通过复用入参来减少空间复杂度
时间复杂度：O(m*n)，空间复杂度：O(1)

算法流程

初始化行数 row 和列数 column，遍历二维数组进行动态规划
状态定义：状态转移二维数组为 dp，dp [i] [j] 表示从 grid[0] [0] 到 grid[i] [j] 得到礼物的最大价值
动态转移方程：
- 当 i=0 && j=0 时，dp[0] [0] = grid[0] [0]
- 当 i=0 && j!=0 时，dp[i] [j] = grid[i] [j] + dp[i] [j-1]
- 当 i!=0 && j=0 时，dp[i] [j] = grid[i] [j] + dp[i-1] [j]
- 当 i!=0 && j!=0 时，dp[i] [j] = grid[i] [j] + max(dp[i-1] [j], dp[i] [j-1])
初始状态：dp[0] [0] = grid[0] [0]
结果值：dp[row-1] [column-1]，row 为二维数组行数，column 为二维数组列数
空间上因为 dp 与 grid 大小一致，可以使用 grid 空间作为 dp 空间，减少空间复杂度

class Solution {
    public int maxValue(int[][] grid) {
        int row = grid.length;
        int column = grid[0].length;
        
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < column; j++) {
                
                if(i == 0 && j == 0) {
                    continue;
                } else if(i == 0) {
                    grid[i][j] += grid[i][j - 1] ;
                } else if(j == 0) {
                    grid[i][j] += grid[i - 1][j];
                } else {
                    grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
                }
            }
        }
        return grid[row - 1][column - 1];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 剑指 Offer 49. 丑数

题目描述

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

1
2
3

说明:

1 是丑数。
n 不超过 1690。

**思路**

标签：动态规划
整体思路：
- 除了第一个丑数外，所有的丑数都是某一个丑数的 2、3 或 5 倍的数字
- 因为要从小到大求第 n 个丑数，所以需要按照顺序每次获取下一个最小的丑数，最终获得第 n 个
复杂度：
- 时间复杂度：O(n)。只需要 n 次遍历即可求得第 n 个丑数
- 空间复杂度：O(n)。需要保存动态规划的整体状态数组

算法流程

状态定义： dp[n] 表示第 n 个丑数，a 表示 2 倍数字的索引用于 dp[a]*2, b 表示 3 倍数字的索引用于 dp[b]*3, c 表示 5 倍数字的索引用于 dp[c]*5
转移方程：
- dp[n] = min(dp[a]*2, dp[b]*3, dp[c]*5)
- 每次计算之后，如果 2 倍的数字最小，则 a++，如果 3 倍的数字最小，则 b++，如果 5 倍的数字最小，则 c++
初始状态： dp[0]=1，因为第一个丑数是 1

class Solution {
    public int nthUglyNumber(int n) {
        int a = 0, b = 0, c = 0;
        int[] dp = new int[n];
        dp[0] = 1;
        for(int i = 1; i < n; i++) {
            int n2 = dp[a] * 2;
            int n3 = dp[b] * 3;
            int n5 = dp[c] * 5;
            dp[i] = Math.min(Math.min(n2, n3), n5);
            
            // 每次计算之后，如果 2 倍的数字最小，则 a++，如果 3 倍的数字最小，则 b++，如果 5 倍的数字最小，则 c++
            if(dp[i] == n2) a++;
            if(dp[i] == n3) b++;
            if(dp[i] == n5) c++;
            
        }
        return dp[n - 1];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 剑指 Offer 62. 圆圈中最后剩下的数字

题目描述

0,1,n-1 这 n 个数字排成一个圆圈，从数字 0 开始，每次从这个圆圈里删除第 m 个数字。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4 这 5 个数字组成一个圆圈，从数字 0 开始每次删除第 3 个数字，则删除的前 4 个数字依次是 2、0、4、1，因此最后剩下的数字是 3。

示例 1：

输入: n = 5, m = 3
输出: 3

1
2

示例 2：

输入: n = 10, m = 17
输出: 2

1
2

限制：

1 <= n <= 10^5
1 <= m <= 10^6

**思路**

标签：动态规划
整体思路：
- 如果依靠暴力枚举的话，每次要遍历 m 个元素，遍历 n 次留下最后一个，时间复杂度达到了O(mn)O(mn) 这道题是著名的约瑟夫环问题，可以将其使用倒推的方式推出来动态规划方程
复杂度：
- 时间复杂度：O(n)。需要进行 n 次递归遍历
- 空间复杂度：O(1)。动态规划可以优化存储空间为常量

算法流程

状态定义：F(n) 表示还有 n 个人时最后剩下的数字索引号，一定要注意！是索引，而不是数字本身！
初始状态：F[1] = 0，因为只剩 1 个数字的时候，索引号从 0 开始，所以一定为 0
转移方程：
- F(1) = 0
- F(2) = (F(1) + m) % 2
- F(3) = (F(2) + m) % 3
- ...
- 从下往上推可以得出方程为
  - F(n)=(F(n−1)+m) % n
因为每个状态的下一步推导只需要上一个状态，所以用一个变量存储即可，不需要使用数组，将时间复杂度降低到O(1)

class Solution {
    public int lastRemaining(int n, int m) {
        int f = 0;
        for (int i = 2; i <= n; i++) {
            f = (f + m) % i;
        }
        return f;
    }
    
    // 动态规划:最容易理解的版本
    public int lastRemaining1(int n, int m) {
        int[] dp = new int[n];
        // f(1,m)解恒为0
        dp[0] = 0;
        for (int i = 1; i < n; i++) {
            // 动态转移方程:f(n,m)=[f(n-1,m)+m]%n
            // 注意:dp[i]时,数组长度为i+1
            dp[i] = (dp[i - 1] + m) % (i + 1);
        }
        return dp[n - 1];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

题目描述

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

1
2
3
4

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

1
2
3

限制：

0 <= 数组长度 <= 10^5

**思路**

标签：动态规划
整体思路：
- 根据题意如果将第x天买，第y天卖进行穷举的话，需要O(n^2)的时间复杂度，所以考虑使用动态规划来降低
复杂度：
- 时间复杂度：O(n)。动态规划需要遍历数组一次
- 空间复杂度：O(1)。只需要记录最小花费和最大收益

算法流程

状态定义： F[n] 表示 prices 中 0-n 下标的子数组的最大利润
转移方程：
- 前 n 天的最大利润 = max(前 n-1 天的最大利润，第 n 天的价格 - 前 n 天的最低价格)
- F[n] = max(F(n-1), min(prices[n], minCost))
初始状态： F[0] = 0
其中只需要记录 minCost 和 F(n-1) 这两个内容即可，不需要留存之前的动态规划记录，进而将空间复杂度从O(n)O(n)降低到了O(1)O(1)

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

1
2
3
4
5
6
7
8
9
10
11

上次更新: 2021/12/22, 10:54:22

← DFS and BFS Untitled→