LeetCode中级算法-动态规划
跳跃游戏
[题目]
给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。
[输入1]
[2,3,1,1,4][返回1]
true解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
[输入2]
[3,2,1,0,4][返回2]
false解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
[解法]
注意数组中的每个元素是你当前最多可以向前跳跃的步数，实际跳跃的步数可以小于当前元素
[代码实现]
package main
import "fmt"
func main() {
input := []int {3,2,1,0,4}
result := computeResult(input)
fmt.Println("result:", result)
}
func computeResult(input []int) bool {
mostPosition := 0
for i := 0; i < len(input); i++ {
if i <= mostPosition {
mostPosition = Max(mostPosition, i + input[i])
if mostPosition >= len(input) - 1 {
return true
}
}
}
return false
}
func Max(a int, b int) int {
if a > b {
return a
}
return b
}不同路径
[题目]
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？
[输入1]
m = 3, n = 7[返回1]
28[输入2]
m = 3, n = 2[返回2]
3[解法]
使用递归法，枚举出所有可能的路径，路径可达就让计数器加一。
[代码实现]
package main
import "fmt"
func main() {
m := 3
n := 2
result := computeResult(m, n)
fmt.Println("result:", result)
}
var count = 0
func computeResult(m int, n int) int {
_compute(0, 0, m, n)
return count
}
func _compute(x int, y int, maxX int, maxY int) {
if x == maxX - 1 && y == maxY - 1 {
count++
return
}
if x < maxX {
_compute(x + 1, y, maxX, maxY)
}
if y < maxY {
_compute(x, y + 1, maxX, maxY)
}
}零钱兑换
[题目]
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
[输入1]
coins = [1, 2, 5], amount = 11[返回1]
3[输入2]
coins = [2], amount = 3[返回2]
-1[解法]
使用递归法，枚举出所有可能的路径，这个题目的解点是当前已经叠加的金额的基础上，尝试叠加给定硬币数组中的一个，要是叠加结果大于设定结果，本次方案作废，要是小于指定的总面额，则继续叠加，要是等于则计数一次，并对比记录是否为最少硬币的情况。
[代码实现]
package main
import "fmt"
func main() {
coins := []int {1,2,5}
input := 11
result := computeResult(coins, input)
fmt.Println("result:", result)
}
var count = 0
func computeResult(coins []int, input int) int {
_compute(0, coins, input, []int{})
return count
}
func _compute(res int, coins []int, total int, resultItems []int) {
if res > total {
return
} else if res == total {
if count == 0 {
count = len(resultItems)
} else {
count = Min(count, len(resultItems))
}
return
}
for i := 0; i < len(coins); i++ {
resItems := append(resultItems, coins[i])
_compute(res + coins[i], coins, total, resItems)
}
}
func Min(a int, b int) int {
if a < b {
return a
}
return b
}最长上升子序列
[题目]
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
[输入]
nums = [10,9,2,5,3,7,101,18][返回]
2[解法]
设立一个指针，从当前第i个元素开始向后遍历，比对指针指向的元素和前一个元素的大小，要是递增则继续移动指针，反之则不是严格递增子序列，记录最长子序列，并从指针指向的位置作为基点，继续向后推移指针检测。
[代码实现]
package main
import "fmt"
func main() {
input := []int {10,9,2,5,3,7,101,18}
result := computeResult(input)
fmt.Println("result:", result)
}
func computeResult(input []int) int {
pointer := 1
maxLen := 0
for i := 0; i < len(input); i++ {
if pointer < i {
pointer = i
}
for pointer < len(input) - 1 {
if input[pointer] > input[pointer + 1] {
maxLen = Max(maxLen, pointer - i + 1)
break
}
pointer++
}
}
return maxLen
}
func Max(a int, b int) int {
if a > b {
return a
}
return b
}