画图和伪代码
Leetcode 198 House Robber
复盘:
可以先不考虑记忆化搜索 , 注释掉
这里有个小错误可以原谅
Leetcode 198 House Robber
go 的 map 要初始化 , 否则是 nil
Leetcode 198 House Robber
边界没定义明确(犯了很多次了)
Leetcode 198 House Robber
Accepted:
package main
import "fmt"
type Solution struct {
memo map[int]int
len int
nums []int
}
func (t *Solution) rob(n int) int {
// n>len return 0
if n>t.len-1 {
return 0
}
max:=-1
for i:=n;i<=t.len-1;i++{
if _,ok:=t.memo[i+2];ok {
max = maxC(max,t.nums[i]+t.memo[i+2])
continue
}
cur:=t.nums[i]+t.rob(i+2)
max=maxC(max,cur)
}
t.memo[n]=max
return max
}
func rob(nums []int) int {
s:=Solution{memo:make(map[int]int),len:len(nums),nums:nums}
res:=s.rob(0)
return res
}
func maxC(v1 int,v2 int) int {
if v1>v2 {
return v1
}
return v2
}
func p(v interface{}) {
fmt.Println(v)
}
func main() {
//r:=[]int{1,2,3,1}
r:=[]int{6,6,4,8,4,3,3,10}
fmt.Println(rob(r))
}
