鲤鱼笔记

动态规划：其他

2021-12-21 每日一题 LeetCode

# 0062. 不同路径 (opens new window)

题目

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

解析

代码

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> f(m, vector<int>(n, 1));
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        return f[m - 1][n - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

# 0063. 不同路径 II (opens new window)

题目

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

解析

代码

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& o) {
        int m = o.size(), n = o[0].size();
        vector<vector<int>> f(m, vector<int>(n));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (o[i][j] == 1) continue;
                if (!i && !j) f[i][j] = 1;
                else {
                    if (i) f[i][j] += f[i - 1][j];
                    if (j) f[i][j] += f[i][j - 1];
                }
            }
        }
        return f[m - 1][n - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 0064. 最小路径和 (opens new window)

题目

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

解析

代码

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> f(m, vector<int>(n, INT_MAX));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!i && !j) f[i][j] = grid[i][j];
                else {
                    if (i) f[i][j] = min(f[i][j], f[i - 1][j] + grid[i][j]);
                    if (j) f[i][j] = min(f[i][j], f[i][j - 1] + grid[i][j]);
                }
            }
        }
        return f[m - 1][n - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 0070. 爬楼梯 (opens new window)

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

解析

斐波那契数列。

代码

class Solution {
public:
    int climbStairs(int n) {
        vector<int> f(n + 2);
        f[1] = 1, f[2] = 2;
        for (int i = 3; i <= n; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11

# 0091. 解码方法 (opens new window)

题目

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
1
2
3
4

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

  • "AAJF" ，将消息分组为 (1 1 10 6)
  • "KJF" ，将消息分组为 (11 10 6)

注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

解析

有条件的斐波那契数列。

代码

class Solution {
public:
    int numDecodings(string s) {
        int n = s.length();
        s = ' ' + s;
        vector<int> f(3);
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            f[i % 3] = 0;
            int a = s[i] - '0', b = (s[i - 1] - '0') * 10 + a;
            if (a >= 1 && a <= 9) f[i % 3] += f[(i - 1) % 3];
            if (b >= 10 && b <= 26) f[i % 3] += f[(i - 2) % 3];
        }
        return f[n % 3];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 0096. 不同的二叉搜索树 (opens new window)

题目

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

解析

用 f(i)f(i) 来表示从 11 到 ii 这 ii 个节点构成的互不相同的二叉搜索树的数量，只要枚举 11 到 ii 这 ii 个数作为根节点，把方案数累加就可以了。

假设当前选定的根节点是 jj，那么左子树的可能构造数就是 11 到 j−1j - 1 这部分节点的构造方案数，也就是 f(j−1)f(j - 1)，右子树的话，是从 j+1j + 1 到 ii 这部分节点的构造方案数，因为构造数量只与节点数有关，所以右子树的方案数量就是 f(i−j)f(i - j)。

这样状态转移方程就是 f(i)=∑j=1if(j−1)×f(i−j)f(i) = \sum_{j=1}^{i}f(j-1)\times f(i-j)。

代码

class Solution {
public:
    int numTrees(int n) {
        vector<int> f(n + 1);
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                f[i] += f[j - 1] * f[i - j];
            }
        }
        return f[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

# 0120. 三角形最小路径和 (opens new window)

题目

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

解析

从下到上递推，可以避免边界处理，同时可以看到每个位置只和下一行的状态有关，所以可以将状态数组压缩至一维。

代码

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<int> f(n + 1);
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                f[j] = min(f[j], f[j + 1]) + triangle[i][j];
            }
        }
        return f[0];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

# 0121. 买卖股票的最佳时机 (opens new window)

题目

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

解析

枚举每个位置，在与历史最低价差值最大的价格卖出。

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0, minPrice = prices[0];
        for (int i = 1; i < prices.size(); i++) {
            ans = max(ans, prices[i] - minPrice);
            minPrice = min(minPrice, prices[i]);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11

# 0123. 买卖股票的最佳时机 III (opens new window)

题目

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

解析

前后缀分解，预处理左右两侧数组进行一笔交易的最大利润，预处理方法同 0121. 买卖股票的最佳时机，找到两笔交易利润和的最大值即可。

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<int> left(n), right(n);
        for (int i = 1, minPrice = prices[0]; i < n; i++) {
            left[i] = max(left[i - 1], prices[i] - minPrice);
            minPrice = min(minPrice, prices[i]);
        }
        for (int i = n - 2, maxPrice = prices[n - 1]; i >= 0; i--) {
            right[i] = max(right[i + 1], maxPrice - prices[i]);
            maxPrice = max(maxPrice, prices[i]);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = max(ans, left[i] + right[i]);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 0152. 乘积最大子数组 (opens new window)

题目

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

解析

本题与 0053. 最大子序和 的思路相似，但由于是乘法运算，负数相乘可能得到最大值，因此在遍历的同时需要维护最大值和最小值两个变量。

代码

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int ans = nums[0];
        int f = nums[0], g = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            int a = nums[i], fa = f * a, ga = g * a;
            f = max(a, max(fa, ga));
            g = min(a, min(fa, ga));
            ans = max(ans, f);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Last Updated: 2023-01-28 4:31:25