*话说在前面
在 @Zhipeng Guan 的怂恿下,参加 ATRS。
因为自己平实比较懒散,时间久了沉淀的东西并不多。希望自己能坚持下去,把内功心法和基础搞扎实一点。
很庆幸遇到一群上进的朋友,大家一起进步😆
Algorithm
https://leetcode-cn.com/problems/climbing-stairs/
这周跟动态规划杠上了,爬楼梯是最基础的动态规划题,由此了解动态规划的思想。
from functools import lru_cache
class Solution:
# 1. 自顶向下,缓存提高性能
@lru_cache(maxsize=50)
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
elif n == 2:
return 2
else:
return self.climbStairs(n-1) + self.climbStairs(n-2)
# 2. 自底向上,性能最优
def climbStairs1(self, n: int) -> int:
a,b = 0,1
for i in range(n):
a = a+b
a,b = b,a
return b
Review
https://medium.com/@gilfink/building-a-chrome-extension-using-react-c5bfe45aaf36
如何使用 react 开发 chrome 扩展
因为有了个 idea 想写个扩展,搜索一番找到了这篇文章,感觉不错。按照指引顺利开工。这是我写的扩展:https://github.com/mayneyao/InfoCard
Tip
自顶向下,自底向上。经常会听到这2个概念,这到底是什么意思?
计算机科学中有两条截然相反的路径。一条是自下而上,从底层指令开始往上抽象(优先考虑性能),逐渐靠近数学。比如,一开始的 Unix 操作系统是用汇编写的,后来发现用汇编写程序太痛苦了,需要一些抽象,所以出现了高级语言 C,再后来由于各种编写应用的需求,出现了更高级的语言如 Python 和 JavaScript。另一条路径是自上而下的,直接从数学开始(Lambda 演算),不考虑性能和硬件状况,按需逐渐减少抽象。前一条路径明显占了主流,代表语言是 Fortran, C, C++, Pascal, 和 Java 等。后面一条路径不够实用,比较小众,代表语言是 Algo, LISP 和 Haskell 等。
参见:https://juejin.im/post/5c2b93c8e51d456d14582b93
结合爬楼问题,可以很好的理解这两种思想。
自顶向下
当前的问题,分解成小问题,逐步求解。以爬楼梯的问题为例,想要知道爬到第十层有多少种解法,要先知道爬到第九层和第八层有多少种解法,以此类推。
f(10) = f(9)+f(8)
f(9) = f(8)+f(7)
-
观察他们之间的关系,归纳出通项公式。f(n) =f(n-1)+f(n-2)
-
找到边界条件
n=1 时 f(n) = 1
n=2 时 f(n) =2
-
递归求解
自顶向下常常伴随着递归,而递归往往性能较差。可以看到 计算f(10)和f(9)的时候 f(8)被计算了2次。可以通过缓存,优化性能。
自底向上
反过来,要知道f(10),先知道 f(9),以此类推,先求出f(1),再求出f(2)... 以此推出f(10)
f(1)=1
f(2)=2
f(3) = f(1)+f(2) =3
f(4)= f(3)+f(2)=2+3=5
....
自底向上常常以循环迭代实现,性能优先。
任何C或Fortran程序复杂到一定程度之后,都会包含一个临时开发的、不合规范的、充满程序错误的、运行速度很慢的、只有一半功能的Common Lisp实现。
问题越复杂,自底向上的求解就越难理清楚。自顶向下看起来会更加清晰优雅,但是往往性能不好。
Share
-
Firefox 推出的匿名文件共享服务 fsend ,项目开源。
GoogleMozilla 人类的希望! -
SICP 视频教程,第一节对自顶而下 诠释得很清晰。(强烈推荐)
-
什么是动态规划?动态规划的意义是什么? - 阮行止的回答 - 知乎 https://www.zhihu.com/question/23995189/answer/613096905
-
漫画解释,什么是动态规划
-
完整解释 Monad -- 程序员范畴论入门