Go每周刷题第四周

开始进入动态规划 Leetcode 系列。

理论知识点相关的自行补充,老规则,还是从简单的题目入手。

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
}

如果文章对你有所帮助,点赞、转发、留言都是一种支持!
图片

本作品采用《CC 协议》,转载必须注明作者和本文链接
吴亲库里
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!