几道简单的动态规划题

前言

动态规划是求解最优化问题的一种问题,是对问题状态的定义和状态转移的定义。一般分两步进行:

  1. 找到最优化问题与子问题的关系,及写出状态转移方程
  2. 找到特殊的边界情况或递归的触底条件

最小路径和

问题描述:给定一个只含非负整数的m*n网格,找到一条从左上角到右下角的可以使数字和最小的路径。

解决思路:求m行,n列的最小路径,及求m-1行,n列的值与m行,n-1列的最小值,再加上本身。所以用表格rec表存每个位置的最小值,状态转移方程为:rec[m][n] = min(rec[m-1][n], rec[m][n-1]) + grid[m][n];边界情况,第一行和第一列只能往右走,往下走。
代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def minPathSum(grid):
m = len(grid)
n = len(grid[0])
rec = [[0]*n for i in range(m)]
for i in range(m):
for j in range(n):
if i == 0 and j == 0:
rec[i][j] = grid[i][j]
elif i > 0 and j > 0:
rec[i][j] = min(rec[i-1][j], rec[i][j-1]) + grid[i][j]
elif i > 0:
rec[i][j] = rec[i-1][j] + grid[i][j]
elif j > 0:
rec[i][j] = rec[i][j-1] + grid[i][j]
return rec[m-1][n-1]

不同的路径

问题描述:有一个机器人的位于一个 m × n 个网格左上角。机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。问有多少条不同的路径?

解决思路:还是用rec来记录路径数,方程为rec[m][n] = rec[m-1][n] + rec[m][n-1];边界情况,第一行和第一行所有值都为1,所以初始值设为1。
代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def uniquePaths(m, n):
rec = [[1]*n for i in range(m)]
for i in range(1, m):
for j in range(1, n):
rec[i][j] = rec[i-1][j] + rec[i][j-1]
return rec[m-1][n-1]

# 递归
def unique(m, n):
if m < 1 or n < 1:
return 0
if m == 0 and n == 0:
return 1
else:
return unique(m-1, n) + unique(m, n-1)

不同的路径II

问题描述:现在考虑网格中有障碍物,那样将会有多少条不同的路径?网格中的障碍和空位置分别用 1 和 0 来表示。

解决思路:如果网格中有1,则该点的路径值为0,其余如上。
代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def uniquePathsII(grid):
m = len(grid)
n = len(grid[0])
rec = [[1]*n for i in range(m)]
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
rec[i][j] = 0
elif i == 0:
rec[i][j] = rec[i][j-1]
elif j == 0:
rec[i][j] = rec[i-1][j]
else:
rec[i][j] = rec[i-1][j] + rec[i][j-1]
return rec[m-1][n-1]

----------本文完,感谢您的阅读----------