动态规划之棋盘路径问题
- 2019 年 10 月 6 日
- 筆記
动态规划之棋盘路径问题
1.对比
DP vs 回溯 vs 贪心
- 回溯(递归) – 重复计算
- 贪心 – 永远局部最优
- DP – 记录局部最优子结构/多种记录值
2.棋盘路径问题
问题描述:
如下图所示,小人从左上角移动到右下角,总共有多少种走法.
约束条件为:粉红色为石头,走不通,小人走路方向只有向下与向右.
该问题可以分解f(0,0)=0,f(1,0)=1,f(0,1)=1 f(m,n)=f(m-1,n)+f(m,n-1)(此时m,n不为0)。
|
0(A) |
1 |
|---|---|
|
1 |
2(B) |
如上表所示为从棋盘中取出的左上角4个格子,填充的数据中第二行第二列(index假设从1开始)为2,表示从A到B有2种路径,依次往下走,最终得到f(m,n)=f(m-1,n)+f(m,n-1)(此时m,n不为0)。
因此该问题是递归问题,同时可以通过动态规划解决。
3.判断是石头还是空地
上述棋盘有个很强的约束条件,就是棋盘的约束问题,粉红色假设为石头,没有粉红色为空地,那我们就是要找到空地,从空地进行行走,下面来编写这样的函数。
棋盘假设为grid的二维数组,共有m行,n列。生成的二维数组中1表示石头，0表示空位。
棋盘生成代码：
import numpy as np m,n = 8,8 grid = np.zeros((m,n),dtype=np.int) for i in range(m): for j in range(n): if (i==1 and (j==2 or j==6)) or (i==2 and j==4) or (i==3 and (j==0 or j==2 or j==5)) or (i==4 and j==2) or (i==5 and (j==3 or j==4 or j==6)) or (i==6 and (j==1 or j==5)): grid[i][j]=1 print(grid)
输出：
[[0 0 0 0 0 0 0 0] [0 0 1 0 0 0 1 0] [0 0 0 0 1 0 0 0] [1 0 1 0 0 1 0 0] [0 0 1 0 0 0 0 0] [0 0 0 1 1 0 1 0] [0 1 0 0 0 1 0 0] [0 0 0 0 0 0 0 0]]
判断该棋盘中某行某列是否是空地：
# 判断是否是空地 def validSquare(grid,m,n): if grid[m][n]==1: return False return True
4.递归法
- 每次先判断当前是否是空地
- 左上角处理
- 每次递归都可以划分为(1,0)或(0,1)子问题
- 第一行与第一列递归
- 中间行列数据递归
def countPath(grid,m,n): # 是否为空地，grid中0为空地，1为非空地 if not validSquare(grid,m,n): return 0 # 左上角特殊处理 if (m==0 and n==0): return 0 # (0,1)与(1,0)为1 if ((m == 0 and n == 1) or (m == 1 and n == 0)): return 1 # 第一行，第一列特殊处理 elif ((m == 0) and (n>1)): return countPath(grid, m, n - 1) elif ((n == 0) and (m>1)): return countPath(grid,m-1,n) # 其他则递归 return countPath(grid,m, n - 1) + countPath(grid,m - 1, n) # 申请dp数组 dp = np.zeros((m,n),dtype=np.int) print(countPath(grid,m-1,n-1))
5.动态规划
从左上角到右下角直接使用递推式，找到动态规划的状态转移方程，然后返回最后的一个数据即可。
我们知道当第一行或者第一列中有石头的时候，随之后面的行或者列就走不通了，那么直接设为0即可。
所以第一步先堆特殊的第一行与第一列进行处理。
然后堆中间行与列处理。
def countPath2(grid,m,n,dp): # 处理每一行 for i in range(m): if not validSquare(grid,i,0): for j in range(i,m): dp[j][0]=0 break dp[i][0]=1 # 处理每一列 for i in range(n): if not validSquare(grid,0,i): for j in range(i,m): dp[0][j]=0 break dp[0][i]=1 # 左上角处理 dp[0][0]=0 for i in range(1,m): for j in range(1,n): if validSquare(grid,i,j): dp[i][j]=dp[i-1][j]+dp[i][j-1] else: dp[i][j]=0 return dp[m-1][n-1]
由于从左上角到右下角与从右下角到左上角路径对称，那么我们可以再写一个从右下角到左上角来验证之前的代码正确性，如果正常，则两次结果是一样的！
下面为从右下角到左上角的动态规划代码：
def countPath1(grid,m,n,dp): # 处理每一行 for i in range(m-1,-1,-1): if not validSquare(grid,i,n-1): for j in range(i,m): dp[j][n-1]=0 break dp[i][n-1]=1 # 处理每一列 for i in range(n-1,-1,-1): if not validSquare(grid,m-1,i): for j in range(i,m): dp[m-1][j]=0 break dp[m-1][i]=1 dp[m-1][n-1]=0 for i in range(m-2,-1,-1): for j in range(n-2,-1,-1): if validSquare(grid,i,j): dp[i][j]=dp[i+1][j]+dp[i][j+1] else: dp[i][j]=0 return dp[0][0]
