【LC#39270】判断子序列爬楼梯（dp算法 第一期）

392. 判断子序列 - 力扣（LeetCode）

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

致谢：

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

示例 1：输入：s = "abc", t = "ahbgdc"
输出：true
示例 2：输入：s = "axc", t = "ahbgdc"
输出：false提示：0 <= s.length <= 100
0 <= t.length <= 10^4
两个字符串都只由小写字符组成。

面对这道题第一问，最简单直接的方法就是双指针，定义一个指针p1指向匹配字符串s，定义p2指向原字符串t；

1. 因为两个字符串都只由小写字符组成，所以如果p2遇到末尾符号，则立刻结束并返回错误

2. 如果p1元素与p2元素相等，则p1 p2都++；

3. 如果不相等，则只给p2++；

4. 如果 p1能够遍历到结束标志，说明匹配完成，退出循环并返回正确

实现代码

bool isSubsequence(char* s, char* t) {int p1=0,p2=0;while(*(p1+s)!='\0'){if(*(p2+t)=='\0'){return false;}if(*(t+p2)==*(s+p1)){p1++;}p2++;}return true;
}

不写注释了，代码很短很简单。

 

进阶问题！！！（动态规划）

如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

这种情况下，想要用第一种方法快速高效解决问题根本不可能。因为第一种方法时间复杂度为：

                                                      T（M，N）= O（M+N）

M若是扩张到十亿的数量级，CPU的负担是很大的。

这里，我们引入一个新的算法 动态规划。

我们先不看这个问题本身，先思考下面一个最经典的爬楼梯问题：

70. 爬楼梯 - 力扣（LeetCode）

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？示例 1：输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶提示：1 <= n <= 45

这个问题大家应该在某个电影里看过哈哈，主角还是占扑算出来的

《少年班》细节解析：王大法用龟壳解题，现实中可能实现吗？_哔哩哔哩_bilibili

咱们先不去想占扑可不可能，咱们思考一下如何在计算机系统解决这个问题？

从最简单的开始，如果爬3阶楼梯，有哪几种爬法？

1. 第一脚 1 第二脚 2

2. 第一脚 2 第二脚 1

3. 第一脚 1 第二脚 1 第三脚 1

统计过后可以得出是三种，但是我们是否发现一个规律呢？

如果我们假设达到第i个台阶的走法为dp[ i ], 那么我们能倒推出两种到达 i 的情况，第一种是从第i-1个台阶走一步到达i，另外一种是从i-2个台阶走两步到达i

那么，到第i个台阶的走法不就等于到i-1走法，和到i-2走法之和吗？

这样我们可以列出如下公式：

                                               dp[i] = dp[i-1] + dp[i-2]

这个公式，叫做动态规划的  状态转移方程  （state transition equation）

咋样，是不是有点像现代控制理论里的状态转移矩阵推导？确实，这种算法和对应思想也是为各行各业的数学建模打下了基础，所以哪里都能看到它的影子。

其次，斐波那契数列也是在这个规律下形成的。

好了，那我们唠嗑完毕后，应该仔细想一想这个算法该如何写了：

1. 开辟一串长为n+1的整形内存dp用于迭代求和（这里为什么是n+1？因为在定义数据结构时，开发者们经常会绕开起点0避免标签出错，包括各类教科书、考研大纲中也会出现这样的写法，换言之我们的计算从dp[1]和dp[2]开始 ，当然你不觉得0开始太抽象的话也可以呢样写）

2. 接着，根据上面3阶情况分析，设定dp[1] = 1, dp[2] = 2

3. 接下来进入一个循环，不断计算dp[i] = dp [i-1] + dp[i-2], 直到i=n+1结束；

4. 输出结果sum = dp [n];

代码实现

int climbStairs(int n) {if(n==1){return 1;}//首先明确一点，循环算法对1阶和2阶情况不起作用，所以要对这两个单独处理if(n==2){return 2;}int* dp = (int *)malloc((n+1)*sizeof(int));//可以在堆区分配dp内存，当然也可以在栈区定义一个动态数组//只要能求出最后一个元素并赋值给sum就符合要求dp[1]=1;dp[2]=2;//一切从1 2阶的基本事实开始for (int i=3; i<n+1; i++){dp[i] = dp [i-1] + dp [i-2];//不断利用状态转移方程进行迭代求解}int sum= dp[n];free(dp);//如果用了堆区内存，一定要提前释放，不然会内存泄漏。//此外，得用一个sum把最后一个元素（我们的结果）保存住return sum;//这里保存的动态变量sum就起到了返回作用
}

        像这样，通过定义一维状态数组 dp[i] 表示与单一维度变量 i 相关的子问题最优解，并基于前序状态递推转移方程 dp[i]=f(dp[0..i−1]) 求解问题的动态规划方法，需设定初始条件并按顺序计算状态值的算法，我们称作一维动态规划。

        一维动态规划有很多典型例题，比如爬楼梯、打劫问题、换零钱等，其中某些问题使用贪心算法也能勉强解决，但是对于大部分问题而言，贪心所需的局部最优解是很难寻找的。所以，想要每道OJ都躺着AC，掌握动态规划是极其重要的。

        接下来我们重新思考这个子序列问题进阶，题解将在下一期放出。

如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，
你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？