问题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欢迎指出
网友评论