golang实现剑指offer：动态规划题型

丑数

LeetCode 面试题49：丑数

题目描述

我们把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例：

输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

核心思想：

• 动态规划

• 三指针

解题思路：

• 已知丑数只包含因子 2, 3, 5，因此第N个丑数一定是 前面某个丑数 * 某个因子（2,3,5）得到

• 我们可以创建一个数组，里面的数字是排好序的丑数，里面的每一个丑数是前面的某丑数乘以2、3或者5得到的

• 定义三个指针p2,p3,p5，它们指向的数字分别只 X 2,X3,X5

• 每次基于p2，p3，p5指向的数字计算出三个丑数，取最小的minVal

• 将minVal添加进数组

func nthUglyNumber(n int) int {
    if n < 1 {
        return 1
    }
    dp := make([]int, n)
    //第一个丑数，即1
    dp[0] = 1
    //三指针初始指向数组第一个元素
    p2, p3, p5 := 0, 0, 0
    cur := 1

    for cur < n {
        //计算丑数，取最小值
        minVal := min(dp[p2]*2, dp[p3]*3, dp[p5]*5)
        dp[cur] = minVal
        // 每次谁计算出来，谁的指针就后移一位
        if minVal == dp[p2]*2 {
            p2++
        }
        if minVal == dp[p3]*3 {
            p3++
        }
        if minVal == dp[p5]*5 {
            p5++
        }
        cur++
    }
    return dp[cur-1]
}

func min(a, b, c int) int {
    if a < b {
        if a < c {
            return a
        }
        return c
    }

    if b < c {
        return b
    }
    return c
}

礼物的最大价值

LeetCode 面试题47

题目描述：

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

示例：

输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物</pre>

核心思想：

• 动态规划

• 原地修改，使空间复杂度为O(1)

• 从格子右下角开始计算

解题思路：

• 明确一个点，当前格子只能向右，向下移动

• 计算每个格子最大价值，顺序从右下角开始，从右到左，从下到上。

• 每个格子在计算时，它的右边格子，下边格子最大价值已计算完毕。

• 当前格子最大价值 等于 当前格子价格 加上 max(右边格子最大价值，下边格子最大价值）

func maxValue(grid [][]int) int {
    row := len(grid)
    if row == 0 {
        return 0
    }
    col := len(grid[0])
    if col == 0 {
        return 0
    }
    //从格子最后一行开始
    for i := row - 1; i >= 0; i-- {
        //从最右边一列开始
        for j := col - 1; j >= 0; j-- {
            tmp1, tmp2 := 0, 0
            //获取右边格子的价值
            if j < col-1 {
                tmp1 = grid[i][j+1]
            }
            //获取下边格子的价值
            if i < row-1 {
                tmp2 = grid[i+1][j]
            }
            //比较，计算当前格子最大价值，原地修改
            grid[i][j] = grid[i][j] + max(tmp1, tmp2)
        }
    }
    return grid[0][0]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}