Leetcode70
这是道入门级的题目。
求 n 级台阶的总方法数。
到达最后一步 n ，只会有两种情况，一种是从 n-1(跨了一步)，另一种从 n-2 (跨了两步)上来的。所以，
f(n)=f(n-1)+f(n-2)。
因为每次只能爬 1 阶 或者 2 阶，所以 f(n) 只能从 f(n-1) 和 f(n-2) 转移上来，这就意味着 n 阶梯总方法数量必然是爬上 n-1 阶梯方法数量 + 爬上 n-2 阶梯方法数量。
进一步说，你要想知道 n 阶方法数，那么就必须先知道 f(n-1) 方法数 和 f(n-2) 方法数，你要想知道 f(n-1) 方法数，就必须......,
# 在下面的程序中表现为 res[n]=res[n-1]+res[n-2]
func climbStairs(n int) int { if n <= 2 { return n } res := make([]int, n+1) // 如果是一个台阶那么就只有一种走法 res[1] = 1 // 如果是两个阶就有两种走法，一种一步一步走两步，一种直接两步 res[2] = 2 for i := 3; i <= n; i++ { res[i] = res[i-1] + res[i-2] } return res[n] }
时间复杂度 O(n)。空间复杂度O(n)。空间复杂度我们可以压缩成 O(1)。因为我们不需要关心太多之前的数据。
func climbStairs(n int) int { if n <= 2 { return n } a, b, ret := 1, 1, 0 for i := 2; i <= n; i++ { ret = a + b b = a a = ret } return ret }
Leetcode198
这是一道超高频的动态规划面试题，它有一个系列的，今天我们来看它的初始版本。
相邻的两家不能偷。如果输入的只有一家，那么不用想了，就偷唯一的那户人家。如果有两家，那么偷的必然是两家中钱多的那家，
那如果总数大于 2 家呢？
对于第 n 家来说，只有两种选择偷或者不偷。
- 如果偷了，那么当前偷窃总金额=之前 n-2 间房屋偷窃的最高金额+第 n 间房屋金额。
- 如果不偷，那么当前偷窃总金额=之前 n-1 间房屋的最高金额。
只要对比这两个选择，取最大的值，就是前 n 间房屋能偷到的最多的钱。伪公式如下，
res[n]=max(res[n-1],res[n-2]+nums[n]
func rob(nums []int) int { if len(nums) == 0 { return 0 } if len(nums) == 1 { return nums[0] } res := make([]int, len(nums), len(nums)) res[0] = nums[0] res[1]=max(res[0],nums[1]) for i := 2; i < len(nums); i++ { temp := res[i-2] + nums[i] res[i] = max(temp, res[i-1]) } return res[len(res)-1] } func max(x int, y int) int { if x > y { return x } return y }
可以换一种思路，本质上房子有奇数位和偶数位之分。只要在抢奇数位或者偶数位的同时进行比较当前最大值，更新到当前奇数位或者偶数位最高金额即可。
func rob(nums []int) int { a := 0 // 奇数值 b := 0 //偶数值 for i := 0; i < len(nums); i++ { if i%2 == 0 { b = max(a, b+nums[i]) } else { a = max(b, a+nums[i]) } } return max(a, b) } func max(x int, y int) int { if x > y { return x } return y }
