数据结构与算法——从递归入手一维动态规划【2】

前言：

记录一下对左程云系列算法课程--算法讲解066【必备】的剩余习题的学习。本文主要简单记录个人学习心得和提供C++版本代码。如需要题目的细致讲解，请前往原视频。

涉及内容：

动态规划、三指针、

参考视频：

左程云--算法讲解066【必备】从递归入手一维动态规划

题目列表：

1.Leetcode--264. 丑数 II

2.Leetcode--32. 最长有效括号

3.Leetcode--467. 环绕字符串中唯一的子字符串

4.Leetcode--940. 不同的子序列 II

题目解答：

⭐1.Leetcode--264. 丑数 II

题目：

解题思考：

首先可以很好的考虑到暴力求解，我们只需要从1开始，从大到小每个数字遍历判断其是否是丑数然后计数即可，但很显然这会超时。

那么我们从质因子入手，因为一个丑数（除1）外，都是由其他丑数×2 | 3 | 5 得到的，那么我们可以从1出发，会得到三个丑数：2、3、5，所以1后面的丑数就是2。接着从2出发，得到三个丑数：4、6、10，算上之前得到但是没有使用的丑数一共是：3、4、5、6、10，所以2后面的数字应该是3，之后循环即可。从上述思路知道我们需要一个优先队列（最小堆），关于C++中priority_queue的比较器我在这里由所记录，按需观看。

可以优先队列会随着时间的推移而变大，而且在得到最终结果时，有很多用不到的数据也会被一直存储。例如刚才我们求第三个丑数（3）时已经计算了5个数。

通过观察，我们可以只保存三个变量，分别指代*2、*3、*5，当对应变量被使用时，我们只需要改变这一个变量即可，即优化了优先队列的空间，还对比较的数据范围进行缩小化。

三版的示例代码如下。

示例代码：

①暴力（超时）

class Solution {public: int nthUglyNumber(int n) { int count = 0; int num = 0; while(count < n){ num++; if(isUglyNumber(num)){ count++; } } //count == n return num; } bool isUglyNumber(int n){ if(n <= 0){ return false; } while(n % 2 == 0){ n /= 2; } while(n % 3 == 0){ n /= 3; } while(n % 5 == 0){ n /= 5; } if(n == 1){ return true; } return false; }};

②优先队列（最小堆）

class Solution {private: struct compare{ bool operator()(unsigned long long a, unsigned long long b){ return a > b; } };public: int nthUglyNumber(int n) { priority_queue<unsigned long long, vector, compare> pq; unsigned long long num = 1; int count = 1; while(count != n){ count++; pq.push((unsigned long long)num * 2); pq.push((unsigned long long)num * 3); pq.push((unsigned long long)num * 5); num = pq.top(); while(num == pq.top()){ pq.pop(); } } return num; }};

③三指针动态规划

class Solution {public: int nthUglyNumber(int n) { vector dp(n + 1, 0); dp[1] = 1; int i2 = 1, i3 = 1, i5 = 1; for(int i = 2; i <= n; i++){ int a = dp[i2] * 2; int b = dp[i3] * 3; int c = dp[i5] * 5; dp[i] = min(min(a, b), c); if(dp[i] == a) { i2++; } if(dp[i] == b) { i3++; } if(dp[i] == c) { i5++; } } return dp[n]; }};

辅助题目与示例代码：

这里再推荐一些相关习题，只是和本题相关，与动态规划无关。

①Leetcode--231. 2 的幂

class Solution {public: bool isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }};

②Leetcode--263. 丑数

class Solution {public: bool isUgly(int n) { if(n  0 && (n & (n - 1)) == 0; }};

⭐2.Leetcode--32. 最长有效括号

题目：

解题思考：

本题的动态规划做法中存在着KMP算法的影子。首先对于暴力求解，我们只需要枚举以每一位为结尾的子括号串的有效括号串长度，最后求最大值即可。但很显然这存在重复计算，那么如何利用之前已经计算过的数据，这就是该题动态规划做法的来历。、

如果当前位置为左括号\"(\"，很显然依此结尾的字串不可能有效，对应dp数组我们记作0。

如果当前位置为右括号\")\"，我们可以看dp[i - 1]位置对应的有效字串长度是多少，这个时候我们只需要关注p = i - dp[i - 1] - 1这个位置是否为\"(\"。如果是，则可以在dp[i - 1]的基础上再加上两个字符长度。最后判断dp[p - 1]位置有多长的有效字符串长度，再次加上即可。

此时只需要加到dp[p - 1]即可，再左边就不用看了，因为我们按照顺序求解，dp[p - 1]的值已经是最长的有效字符串长度了。

 这里还是推荐一下原视频的，左老师模拟了一个很长的例子帮助有效理解，最后代码如下。

示例代码：

class Solution {public: int longestValidParentheses(string s) { if (s == \"\") { return 0; } int n = s.size(); vector dp(n, 0); dp[0] = 0; int ans = 0; for(int i = 1; i = 0 && s[p] == \'(\'){  dp[i] = dp[i - 1] + 2 + (p > 0 ? dp[p - 1] : 0); } } ans = max(ans, dp[i]); } return ans; }};

⭐3.Leetcode--467. 环绕字符串中唯一的子字符串

题目：

解题思考：

最容易想到的暴力解法当然是逐个位置进行枚举，显然，重复计算非常多。而观察可发现长字符串是包含短字符串的，所以很自然可以联系到状态方程。但这里重点不在如何建立状态方程，状态方程只是\"果\"。我们要找的是字串之间的关系，即\"因\"。

如果我们以每个位置作为字串的开头去判断是否为有效字串，则从0位置开始显然是最复杂的，那么这时可以考虑从末位置，即从右向左，但这可能写不顺手。所以我们可以使每个位置作为字串的结尾，从左向右即可。

那么从0位置入手，很显然其对应的字串为1。在下一个位置时，我们查看上一个位置是否能连在一起构成有效字串，如果是有效字串，则以此位置结尾的有效字串最大长度为len+ 1，len用于记录当前有效字串最大长度，而我们对26个字母都存放对应字母结尾时，可以构成的有效子串个数，最后循环完毕累加即可。可能表述不是很清楚，这里还是推荐一下左老师的原视频。

示例代码：

class Solution {public: int findSubstringInWraproundString(string s) { int n = s.size(); vector ss(n); for(int i = 0; i < n; i++){ ss[i] = s[i] - \'a\'; } vector dp(26, 0); int len = 1; dp[ss[0]] = 1; for(int i = 1, cur, pre; i < n; i++){ cur = ss[i]; pre = ss[i - 1]; if((pre == 25 && cur == 0) || pre + 1 == cur){ len++; }else{ len = 1; } dp[cur] = max(dp[cur], len); } int ans = 0; for(int x : dp){ ans += x; } return ans; }};

⭐4.Leetcode--940. 不同的子序列 II

题目：

解题思考：

 本题还是看原视频吧。主要特点在于计数和去重，cnt[idx]设计的很好。

示例代码：

class Solution {private: int mod = 1e9 + 7;public: int distinctSubseqII(string s) { vector cnt(26, 0); int all = 1; int newAdd; for(char c : s){ int idx = c - \'a\'; newAdd = (all - cnt[idx] + mod) % mod; cnt[idx] = (cnt[idx] + newAdd) % mod; all = (all + newAdd) % mod; } return (all - 1 + mod) % mod; }};

最后：

关于动态规划的总结其实左老师也讲了很多。这节课最重要的学习了动态规划是怎样来的，即设计纯递归、记忆化搜索、设计递推、空间优化。其实整个过程也就是把递归写成迭代的做法。另外还有对序列的操作，作为初学者的我也很容易将每个位置所为所求序列的开头，但是这样会陷入0位置就是最复杂位置的困难。当我们反向思考，让每个位置最为所求序列的结尾，这样就可以从0位置起依次迭代了。

学习算法是漫长且痛苦的过程，且可能长期伴随着焦虑。但这是始终要面对的，毕竟是自己选择的路。算法难吗？难。需要天赋吗？需要一点。自己有天赋没？不知道。在我看来，天赋只有在经历过无数努力且踩在巨人的肩膀上才能体现的东西。更何况天赋的高山永无顶点，只要实现自我超越，就是有价值的。愿自己能在学习技术和算法的路上一直走下去。