题目

leetcode213:打家劫舍

代码与解析

本文思路参考自carl代码随想录
本道题目是成了一道环,
leetcode:198没有环
成环的话主要是考虑三种情况

  • 不考虑首尾
  • 考虑首,不考虑尾
  • 考虑尾不考虑首

    但是,实际上只需要考虑两种情况,第二种和第三种
    第一种情况被第二种第三种包括了,
    这道题要把每一种情况拆出来,每一种具体情况和leetcode:198没有环很相似

// 实际上nums数组可以值传递,不需要引用传递,虽然这样可以提高效率
func rob(nums []int) int {
    if len(nums)==1{
        return nums[0]
    }
    r1 := pack(0, len(nums)-2, &nums)
    r2 := pack(1,len(nums)-1,&nums)
    return max(r1, r2)
    // fmt.Println(dp)
    // return dp[len(nums)-1]
}
func pack(start, end int, nums *[]int)int{
    // fmt.Println("start:", start, "end:", end)
    if end==start{
        return (*nums)[end]
    }
    dp := make([]int, len(*nums))
    dp[start] = (*nums)[start]

    dp[start+1] = max((*nums)[start], (*nums)[start+1])
    // fmt.Println(dp)
    for i:=start+2;i<=end;i++{
        dp[i] = max(dp[i-2]+(*nums)[i],dp[i-1])
    }
    fmt.Println(dp)
    return dp[end]
}
func max(m,n int)int{
    if m>n{
        return m
    }
    return n
}
分类: 算法

站点统计

  • 文章总数:309 篇
  • 分类总数:19 个
  • 标签总数:190 个
  • 运行天数:975 天
  • 访问总数:72650 人次

浙公网安备33011302000604

辽ICP备20003309号