丑数
题目描述
我们把只包含因子 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
}
礼物的最大价值
题目描述：
在一个 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
}
