# Go每周刷题第四周

## Leetcode70

``f(n)=f(n-1)+f(n-2)。``

`````` 在下面的程序中表现为
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]
}``````

``````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

``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
}``````

(=￣ω￣=)··· 暂无内容！

37

87

434

505