前言
动态规划是求解最优化问题的一种问题，是对问题状态的定义和状态转移的定义。一般分两步进行：
- 找到最优化问题与子问题的关系，及写出状态转移方程
- 找到特殊的边界情况或递归的触底条件
最小路径和
问题描述：给定一个只含非负整数的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]；边界情况，第一行和第一列只能往右走，往下走。 代码实现：
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。 代码实现：
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 == or n == 1:
return 1
else:
return unique(m-1, n) + unique(m, n-1)
不同的路径II
问题描述：现在考虑网格中有障碍物，那样将会有多少条不同的路径？网格中的障碍和空位置分别用 1 和 0 来表示。
解决思路：如果网格中有1，则该点的路径值为0，其余如上。 代码实现：
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]
