70. 爬楼梯 https://leetcode-cn.com/problems/climbing-stairs/
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
解：
暴力，如果只有一阶，就只有一种方法；如果只有二阶，就只有两种方法。那么n阶的方法数就等于n-1阶和n-2阶方法数之和。但直接递归，有太多重复计算，超时。O(2n)
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 2:
return n
return self.climbStairs(n-1) + self.climbStairs(n-2)
递归+记忆化，放数组里缓存。把每一步的结果存储在 memo 数组之中，每当函数再次被调用，就直接从 memo 数组返回结果
class Solution:
def climbStairs(self, n: int) -> int:
memo = [0]*(n+1) # memo[i]表示从第i阶到第n阶的方法数，出发点是第0阶
def helper(i, n, memo): # 起始点i，终点n
if i > n: # 越界，最高起点直接在第n阶
return 0
if i == n: # 不用动，一种方法
return 1
if memo[i] > 0:
return memo[i] # 如果已经算过了，就不用再算了
memo[i] = helper(i+1, n, memo) + helper(i+2, n, memo)
return memo[i]
return helper(0, n, memo)
动态规划，递推， f(n) = f(n-1) + f(n-2) ，f(1)=1 , f(2)=2。O(N) 其实也可以不用开一个数组。
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 2:
return n
f = [0]*n
f[0], f[1] = 1, 2
for i in range(2, n):
f[i] = f[i-1]+ f[i-2]
return f[n-1]
# O(1) 空间
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 2:
return n
pre1 = 1
pre2 = 2
for i in range(2, n):
cur = pre1 + pre2
pre1 = pre2
pre2 = cur
return cur
Binets 矩阵乘法
特征根
120.三角形最小路径和 https://leetcode-cn.com/problems/triangle/
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
说明：
如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。
原文：https://www.cnblogs.com/chaojunwang-ml/p/11365562.html