Leetcode 198 House Robber

画图和伪代码

复盘:
可以先不考虑记忆化搜索 , 注释掉
这里有个小错误可以原谅

go 的 map 要初始化 , 否则是 nil

边界没定义明确(犯了很多次了)

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

本作品采用《CC 协议》，转载必须注明作者和本文链接