(28)Go记忆化搜索和动态规划解决问题

问题1：求爬楼梯方法 //

结构图如下

根据上图，可以推导出：
设c(n)为爬n阶楼梯的方法总数
例1)每次可以爬 1 或 2 个台阶，则c(n)=c(n-1)+c(n-2)
例2)每次可以爬 1 或 2 或 3 个台阶，则c(n)=c(n-1)+c(n-2)+c(n-3)
理解好这点，代码就容易写了

动态规划实现
func climbStairs(n int) int {
    if n < 2 {
        return 1 // 无台阶可走算1种
    }

    memo := make([]int, n+1)
    memo[0] = 1
    memo[1] = 1
    for i := 2; i <= n; i++ {
        memo[i] = memo[i-1] + memo[i-2]
    }
    return memo[n]
}

提交leetcode，通过

问题2：求三角形最短路径和 //

思路：先弄清该三角形的数学关系
第x行有x+1个点，x行y列点的下一行相邻两点坐标是[x+1][y]，[x+1][y+1]
理解好这点，之后写代码较容易

// 解法1:动态规划1--二维空间存储 （理解好解法1有助于理解解法2）
// 定义(n+1)*(n+1)的二维数组minDis[][]int
// minDis[i][j]代表triangle[i][j]到达底部的最短距离,最底层最短距离为本身的值
// minDis[0][0]代表从顶层到最底层的最短距离
// 空间复杂度为O(n^2)
func minimumTotal(triangle [][]int) int {
    n := len(triangle)
    if n == 0 {
        return 0
    }

    // (n+1)*(n+1)二维数组
    // n+1层是为了统一逻辑好写代码
    minDis := make([][]int, n+1)
    for i := 0; i < n+1; i++ {
        minDis[i] = make([]int, n+1)
    }

    // 底层开始遍历
    for i := n - 1; i >= 0; i-- {
        for j, v := range triangle[i] {
            // 相邻的两个点是下一层的j,j+1
            // 默认值均为0,第一层循环结束后,n-1(底层)层存储的是自身的值
            minDis[i][j] = v + min(minDis[i+1][j], minDis[i+1][j+1])
        }
    }
    return minDis[0][0]
}

解法1提交leetcode，通过

由解法1可以看出，triangle[i][j]的最短距离依赖i+1层的正下方和右边，
因此点[i+1][j]前面的值更新为i行的数据，并不会影响i行后续最短距离的更新
triangle[i][j]最短距离的更新可以写成minDis[j] = triangle + min(minDis[j], minDis[j+1])

// 解法2:动态规划2--一维空间存储
// 空间复杂度为O(n)
func minimumTotal2(triangle [][]int) int {
    n := len(triangle)
    if n == 0 {
        return 0
    }

    // (n+1)一维数组
    //+1是为了统一逻辑好写代码
    // minDis[0]为顶层到底层的最短距离
    minDis := make([]int, n+1)

    // 底层开始遍历
    // 第一次循环后,minDis的值即为底层本身的值(距离)
    for i := n - 1; i >= 0; i-- {
        for j, v := range triangle[i] {
            // j更新前为上一层的j位置的最短距离,更新后j为本层最短距离,
            // 而j+1不被改变,在下一次循环中可用来做比较和更新
            minDis[j] = v + min(minDis[j], minDis[j+1])
        }
    }
    return minDis[0]
}

提交leetcode，通过

问题3：打家劫舍 //

展开图如下：

上上图可知：//
设rob[0.n]为偷取[0..n]房子的最佳策略，v[0...n]为房子东西的价值
偷取[0...n]范围的房子，存在n种决策
rob[0...n] = max{v[0]+rob[2...n]，v[1]+rob[3...n]，v[2]+rob[4...n]，...，v[n-2]+rob[n...n]，v[n-1]，v[n]}
所有策略中选择价值最大的一种策略即为最优策略

状态的定义和状态转移方程如下图：

func max(v1, v2 int) int {
    if v1 > v2 {
        return v1
    }
    return v2
}

// 方法1:记忆化搜索
func rob(nums []int) int {
    n := len(nums)
    if n == 0 {
        return 0
    }
    
    // memo[i]表示偷取[i...n-1]所能获得的最大价值
    // 初始值设为-1,表示没有计算过偷取[i..n-1]的最大价值
    memo := make([]int, n)
    for i := 0; i < n; i++ {
        memo[i] = -1
    }
    return tryRob(nums, 0, n, memo)
}

// 考虑抢劫[index...n-1]区间的房子,所能获得的最大收益
func tryRob(nums []int, index, n int, memo []int) int {
    
    // 递归终止条件
    if index >= n {
        return 0
    }
    
    // 递归过程
    if memo[index] != -1 {
        return memo[index]
    }
    
    res := 0 //偷取[index...n-1]的最大价值
    for i := index; i < n; i++ {
        res = max(res, nums[i]+tryRob(nums, i+2, n, memo))
    }
    memo[index] = res
    return res
}

动态规划：
由状态转移方程可以看出rob[n-1...n]，依赖于rob[n...n]的答案，
rob[n-2...n]，依赖于rob[n-1...n]和rob[n...n]的答案，因此可以从尾部开始解答，
一步步扩大区间，最终解[0...n]的问题

// 方法2 动态规划
// 时间复杂度O(n^2)
func rob2(nums []int) int {
    n := len(nums)
    if n == 0 {
        return 0
    }

    // memo[i] 表示考虑抢劫nums[i...n-1]所能获得的最大收益
    memo := make([]int, n)
    memo[n-1] = nums[n-1]

    // 反向遍历,从小问题一步步求解,最后解出大问题
    for i := n - 2; i >= 0; i-- {
        for j := i; j < n; j++ {
            // j+2会越界,越界即没有可以偷的房子,返回nums[j] + 0
            if j+2 >= n {
                memo[i] = max(memo[i], nums[j])
            } else {
                // 遍历前面所有解,找出最优策略
                memo[i] = max(memo[i], nums[j]+memo[j+2])
            }
        }
    }
    return memo[0]
}

TIM截图20190515183828.jpg

提交leetcode，通过

不同的状态定义，有不同的状态转移方程。
将问题3的状态从考虑偷取[index...n-1]区间改成考虑偷取[0...index]区间
动态规划实现则变成以下这样
// 动态规划2：考虑偷取[0...index]范围里的房子
func rob3(nums []int) int {
    n := len(nums)
    if n == 0 {
        return 0
    }

    // memo[i] 表示考虑抢劫nums[i...i]所能获得的最大收益
    // 这样最大值就是memo[n-1]
    memo := make([]int, n)
    memo[0] = nums[0]

    // 正向遍历,从小问题一步步求解,最后解出大问题
    for i := 1; i < n; i++ {
        for j := i; j >= 0; j-- {
            // j+2有会越界,越界即没有可以偷的房子,返回nums[j] + 0
            if j-2 < 0 {
                memo[i] = max(memo[i], nums[j])
            } else {
                // 遍历前面所有解,找出最优策略
                memo[i] = max(memo[i], nums[j]+memo[j-2])
            }
        }
    }
    return memo[n-1]
}

提交leetcode，通过

有bug欢迎指出