引言
本文分享动态规划算法中比较经典的计数问题,帮助大家简单理解动态规划以及题目特点。
1、问题
给定n行m列的矩阵网格,有一个机器人从左上角(0,0)出发,每一步可以向下或者向右移动一步,求解有多少种不同的方式走到右下角(m-1,n-1)。
2、方法
首先初始化一个二维数组,因为这里是有行和列的矩阵,设nums[i][j]为机器人有多少种方式从左上角走到(i,j)。从(0,0)开始移动,机器人在第一行和第一列向任意方向移动的方式都是1,因此我们可以直接将第一行或是第一列的状态标记为1,其他的所有区域中移动方式均为多种,因此利用状态转移方程求解。
3、实验结果与讨论
代码清单 1
# 方法1
n=int(input())
m=int(input())
nums = [[1] * n] + [[1] + [0] * (n - 1) for _ in range(m - 1)]
#print(nums) # 第一行第一列为 1 [[1, 1, 1], [1, 0, 0], [1, 0, 0]]
for i in range(1,m):
for j in range(1,n):
nums[i][j]=nums[i-1][j]+nums[i][j-1]
print(nums[m-1][n-1])
# 方法2 数学方法
# 从左下角到右下角的过程中,我们需要移动m+n-2次,其中m-1次向下移动,n-1次向右移动,因此路径的总数
#就等于从m+n-2中选择m-1或者n-1的组合数
import math
a=math.comb(m+n-2,n-1)
print(a)
4、结语
针对不同路径问题,可以利用动态规划思想和数学思维对问题进行求解,利用动态规划,重点是理解状态转移方程,以及初始化数组的方法。将第一行第一列初始化为1。原问题是求解走到(m-1,n-1),将原问题转化为,机器人有多少种方式从左上角走到(m-2,n-1)和(m-1,n-2),得到状态转移方程。
稿件来源:深度学习与文旅应用实验室(DLETA)
作者:陈相君
主编:欧洋