数据结构与算法 -- 动态规划常见问题
一、简单的路径规划
1、问题描述
问题：一个机器人位于一个 m * n 网格的左上角 （起始点在下图中标记为“开始” ），机器人每次只能向下或者向右移动一步，现在机器人试图达到网格的右下角（在下图中标记为“结束”）。问总共有多少条不同的路径？
示例：
输入：m = 3, n = 2
输出： 3
解释: 从左上角开始，总共有 3 条路径可以到达右下角：
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右2、算法分析
1）备忘录
dp[i][j]表示到i行j列的格子的路径数；
2）初始化状态
因为每次只能向下或者向右进行移动，所以第一行第一列的所有路径数都是1；其他格子路劲数初始化为0；
3）状态参数
状态参数就是i行j列；
4）决策
因为只能向下或者向右移动，因此d[i][j] = d[i-1][j] + d[i][j-1]
3、状态转移方程
4、算法实现
package main
import "fmt"
func DP(m int, n int) int {
// 创建备忘录
dp := make([][]int, m)
for i := range dp{
dp[i] = make([]int, n)
}
// 初始化状态
for i := 0; i < m; i++ {
dp[i][0] = 1
}
for i := 0; i < n; i++ {
dp[0][i] = 1
}
// 转移方程转换实现
for i := 0; i< m; i++ {
for j := 0; j < n; j++ {
if i == 0 || j == 0 {
dp[i][j] = 1
} else {
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}
}
return dp[m-1][n-1] // 输出答案
}
func main() {
m := 3
n := 7
fmt.Println(DP(m, n)) // 输出答案
}二、带路障路径规划
1、问题描述
问题：一个机器人位于一个 m * n 网格的左上角 （起始点在下图中标记为“开始” ）。机器人每次只能向下或者向右移动一步，现在机器人试图达到网格的右下角（在下图中标记为“结束”）。考虑网格中有障碍物，网格中的障碍物和空位置分别用 1 和 0 来表示，那么从左上角到右下角将会有多少条不同的路径？
示例：
输入：
[
[0, 0, 0],
[0, 1, 0],
[0, 0, 0]
]
输出: 2
解释：3 * 3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右2、算法分析
1）备忘录
dp[i][j]表示到i行j列的格子的路径数；
2）初始化状态
依然先考虑网格的第一行和第一列，第一行永远只能从左侧的格子往前走；第一列永远只能从上方的格子往下走。由于我们只能向右或向下走，所以第一行和第一列的格子永远只能存在 1 条路径。但是，我们还需要再考虑那些有障碍的格子，对这些格子来说，它们的路径总数应该是 0 而不是 1。
3）状态参数
状态参数就是i行j列； 状态参数依然是格子的行数和列数；
4）决策
因为只能向下或者向右移动，因此d[i][j] = d[i-1][j] + d[i][j-1] ；有障碍物的格子的路径数为0；
3、状态转移方程
4、算法实现
package main
import "fmt"
func DP(m int, n int, array [][]int) int {
// 创建备忘录
dp := make([][]int, m)
for i := range dp{
dp[i] = make([]int, n)
}
// 初始化状态
for i := 0; i < m; i++ {
if array[i][0] == 1 {
dp[i][0] = 0
} else {
dp[i][0] = 1
}
}
for i := 0; i < n; i++ {
if array[0][i] == 1 {
dp[0][i] = 0
} else {
dp[0][i] = 1
}
}
// 转移方程转换实现
for i := 0; i< m; i++ {
for j := 0; j < n; j++ {
if (i == 0 || j == 0) && array[i][j] == 0 {
dp[i][j] = 1
} else if array[i][j] == 1 {
dp[i][j] = 0
} else {
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}
}
return dp[m-1][n-1] // 输出答案
}
func main() {
m := 3
n := 3
array := [][]int{{0, 0, 0},
{0, 1, 0},
{0, 0, 0}}
fmt.Println(DP(m, n, array)) // 输出答案
}三、跳跃游戏
1、问题描述
题目：给出一个非负整数数组 A，你最初定位在数组的第一个位置。数组中的每个元素代表你在那个位置可以跳跃的最大长度。判断你是否能到达数组的最后一个位置。
示例1：
输入：A = [2, 3, 1, 1, 6]
输出： True
解释: 我们可以先跳 1 步，从位置 0 到达位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。2、算法分析
1）备忘录
DP[i] 来表示能否从出发点到达位置 i。
2）初始化状态
初始化状态就是 0 这个位置。因为这个位置是出发点，因此肯定可以到达，所以我们可以将其初始化成 True。
3）状态参数
状态参数也比较容易看出，只有数组的位置是变化的，因此状态参数就是当前位置 i
4）决策
要知道能否到达位置 i，就需要逐个看前面的位置，判定能否从位置 i−1、i−2、i−3 … 跳到位置 i 上。
3、状态转移方程
4、算法实现
package main
import "fmt"
func DP(array []int) bool {
length := len(array)
// 创建备忘录
dp := make([]bool, length)
// 初始化状态
for i := 0; i < length; i++ {
dp[i] = false
}
dp[0] = true
// 转移方程转换实现
for i := 1; i< length; i++ {
for j := 0; j < i; j++ {
if dp[j] && j + array[j] >= i {
dp[i] = true
break
}
}
}
return dp[length-1] // 输出答案
}
func main() {
array := []int{2, 3, 1, 1, 6}
fmt.Println(DP(array)) // 输出答案
}
声明：本文参考极客时间《动态规划面试宝典》