数据结构与算法 -- 动态规划常见问题

一、简单的路径规划

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))  // 输出答案
}

 

声明：本文参考极客时间《动态规划面试宝典》