动态规划2

原创
03/09 16:35
阅读数 45

跳跃问题

给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

示例 1:

输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2:

示例 2:

输入:nums = [3,2,1,0,4]
输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。

审题:

题目中出现“是否能”,结合我们上篇总结的规律,可以推断使用动态规划。

分析问题(也就是转移公式)

  • 如果所有元素都不为0, 那么一定可以跳到最后;
  • 从后往前遍历,如果遇到nums[i] = 0,就找i前面的元素j,使得nums[j] > i - j。如果找不到,则不可能跳跃到num[i+1],返回false。

有,num[0~n] != 0 true。

num[i]=0,则num[j] > i - j, i>j。

代码实现

func canJump(nums []int) bool {
	l := len(nums)
	if l < 2 {
		return true
	}

	var can bool = true
	for i:=l-2;i>-1;i-- {
		if nums[i] == 0 {
			can = false
			for j:=0;j<i;j++ {
				if nums[j] > i - j {
					can = true
					break
				}
			}
			if !can {
				return false
			}
		}
	}
	return can
}

解题注意几个边界问题:

  1. 长度为<2时
  2. 最后一位为0时

算法升级(这里只讨论动态规划)

给定一个非负整数数组,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
	 从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。
func jump(nums []int) int {
	l := len(nums)
	if l < 1 {
		return 0
	}

	dp := make([]int, l)
	dp[0] = 0  //第0个 1步
	           //第1个 第0个+1
	           //第2个 如果之前能到达,为之前数字步数+1
	for i := 1; i < l ; i ++ {
		dp[i] = i  //到达第i步最大值是i
		for j:=0;j<i;j++ {
			if nums[j] >= i-j {
				dp[i] = dp[j]+1
				break
			}
		}
	}
	//发现一个规律,dp的结果是单调递增的,因此,只需要找到第一个能到达当前位置的节点即可
	//fmt.Println(dp)  //[0 1 1 2 2]  [0 1]
	return dp[l-1]
}

总结

常见动态规划类型:

- 坐标型动态规划
- 序列型动态规划
- 划分型动态规划
- 区间型动态规划
- 背包型动态规划
- 最长序列型动态规划
- 博弈型动态规划
- 综合型动态规划
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部