上一次系统整理算法知识是2020年8月到10月,最初打算每周至少刷一道题,但后面就没怎么坚持了。大家有兴趣可以看一下算法系列。
两三个星期前,重新开始做算法题,争取每周完成一道,这么做有几个原因:
警醒:最近看到一些年长的程序员在面试的时候,算法能力并不是很好。虽然随着职位的提升,写代码的时间减少,架构的时间增多,但代码能力不能丢
平常心:不抱任何目的完成一道算法题,感受算法的美感,是难得的体验,而且能够更好的加深对算法的理解
成长:左耳听风提过ARTS,建议大家每周做四件事情
- Algorithm。主要是为了编程训练和学习。每周至少做一个 leetcode 的算法题。
- Review:主要是为了学习英文,需要你阅读并点评至少一篇英文技术文章。
- Tip:主要是为了总结和归纳你在是常工作中所遇到的知识点。学习至少一个技术技巧。
- Share:主要是为了建立你的影响力,能够输出价值观。分享一篇有观点和思考的技术文章。
Review和Tip我都融入到Share中去了,保证每周至少分享一篇文章。这次正好可以把A补上。
计划
这次计划每周从一个类型中选一个题目做,前两周做了数组和字符串,这周就做动态规划。
如果对某个类型的题目掌握的不是特别好,就多做几道题。
无论题目难易,都尽量写写解题思路和感触,能够沉淀下来一些知识。
所有代码都放在github的https://github.com/shidawuhen/asap/tree/master/controller/algorithm ,不知不觉完成一百多个题目了。
括号生成
数字 n
代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例 1:
1 | 输入:n = 3 |
示例 2:
1 | 输入:n = 1 |
提示:
1 <= n <= 8
解题思路
动态规划解题流程
这道题使用动态规划法完成,在算法总结中,整理过动态规划的解题流程:
动态规划法利用问题的最优性原理,以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。应用动态规划法设计算法一般分为3个阶段:
1)分段:将原问题分解为若干个相互重叠的子问题
2)分析:分析问题是否满足最优性原理,找出动态规划函数的递推式
3)求解:利用递推式自底向上计算,实现动态规划过程
这三个阶段其实是有套路的
- 首先反证法证明满足最优性原理
- 推导出动态规划函数 - 这是最重要的一点
- 动态规划函数在推导前要确认该函数满足题目的解
- 可以画图来帮助做动态规划函数的推导
- 记录中间过程 - 这是核心中的核心
思路
一般而言,动态规划的公式为:F(n) = F(p) [+ - * / min max] F(q),然后利用递推/迭代方式进行计算。
每一个括号序列,必然以(开始,必然有对应的),据此抽象出括号序列模型:(a)b,其中a、b分别是一个合法的括号序列(可以为空)。
F(n)=(F(a))*F(b),其中a+b=n-1
假设n为4,则F(4)=(F(0))*F(3)+(F(1))*F(2)+(F(2))*F(1)+(F(3))*F(0),即将F(a)和F(b)进行组合。
抽象出括号序列模式(a)b,然后推导出动态规划公式,是其中的难点。
代码
1 | var allParenthesis map[int][]string |