剑指offer97-100动态规划二维数组

剑指 Offer II 097. 子序列的数目

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，“ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）

题目数据保证答案符合 32 位带符号整数范围。

动态规划

s父串要生成子串t
如果父串长度小于子串长度，那么不可能生成

如果子串为空，那么父串只需要删除自身就能生成，且只有删除自身这一种方式

如果新添加一个元素，这个元素可以是横向添加的一个，也可以是列向添加的一个，但不管横向还是列向添加，都表示父类添加了这个元素
如果这个新添加的元素，行列相同，那么有两种选择
1、父串舍弃这个元素，如下图的横向箭头，也就是我选择不要这个元素
2、父串和子串都舍弃这个元素，如下图的斜箭头，父类和子类都不要这个元素

如果这个新添加的元素不同

python版本

以下图为例，每一行的两个元素生成下一个元素，而最终结果只是求最右下角的值，那么二维数组可以只用一行的一维数组表示，每次一维数组保存上一行的数据，然后逐渐修改下一行的数据

剑指 Offer II 098. 路径的数目

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

输入：m = 3, n = 7
输出：28

动态规划，类似爬楼梯

节省空间，使用滚动的二维数组

如上图所示，仅用2*m就可以，如果再节省一点，让m为n和m中小的那个

 if (m < n) return uniquePaths(n, m);
1

再节省空间，使用一维数组

剑指 Offer II 099. 最小路径之和

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

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

动态规划

对于当前步，有从上面来的和从左边来的，两个选最小的加上当前的花费
和爬楼梯花费最小体力一样

代码

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
       
        vector<vector<int>> dp(grid.size(), vector<int>(grid[0].size()));

        dp[0][0] = grid[0][0];
        for (int j = 1; j < grid[0].size(); ++j) {
            dp[0][j] = grid[0][j] + dp[0][j - 1];
        }

        for (int i = 1; i < grid.size(); ++i) {
            dp[i][0] = grid[i][0] + dp[i - 1][0];
            for (int j = 1; j < grid[0].size(); ++j) {
                dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
            }
        }
        return dp[grid.size() - 1][grid[0].size() - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

抽象成一维数组的代码

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        vector<int> dp(grid[0].size());

        dp[0] = grid[0][0];
        for (int j = 1; j < grid[0].size(); ++j) {
            dp[j] = grid[0][j] + dp[j - 1];
        }

        for (int i = 1; i < grid.size(); ++i) {
            dp[0] = grid[i][0] + dp[0];
            for (int j = 1; j < grid[0].size(); ++j) {
                dp[j] = min(dp[j - 1], dp[j]) + grid[i][j];
            }
        }
        return dp[grid[0].size() - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

剑指 Offer II 100. 三角形中最小路径之和

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

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。