不同路径

简介: 不同路径

引言

本文分享动态规划算法中比较经典的计数问题,帮助大家简单理解动态规划以及题目特点。


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),得到状态转移方程。

目录
相关文章
|
存储 Kubernetes Linux
使用PersistentVolume:怎么解决数据持久化
【8月更文挑战第13天】Kubernetes通过Volume提供数据存储抽象,让用户无需关心底层细节。PersistentVolume (PV) 作为持久存储设备的抽象,由管理员创建并维护,如Ceph、NFS等。PV属系统资源,Pod仅可使用。
使用PersistentVolume:怎么解决数据持久化
|
Nacos 数据安全/隐私保护 Docker
nacos区分权限
nacos区分权限
297 0
|
数据采集 PyTorch API
图片识别转公式,GitHub 又一 LaTeX 神器面世
只需要把公式图片用鼠标拖动到工具内,就能一键转成 LaTex 公式。 写论文、做研究时,最让你头疼的是什么?想必公式编辑会榜上有名。那么有没有便捷的方法进行公式编辑呢?这里推荐一款神器,它使用 PyTorch Lightning 可将 LaTeX 数学方程的图像映射到 LaTeX 代码。 它的效果是这样的,输入一张带公式的图片,它能转换成 LaTeX 代码形式:
|
弹性计算 应用服务中间件 Apache
阿里云2核4G云服务器支持多少人同时在线?并发数计算?
阿里云服务器2核4G支持多少人同时在线?关于2核4G服务器的并发数取决于实际应用程序效率、公网带宽及ECS实例规格,还有2核4G云服务器公网带宽,带宽小的话很可能直接都卡到网络入口了
1175 0
阿里云2核4G云服务器支持多少人同时在线?并发数计算?
|
存储 缓存 算法
学术加油站|基于 RDMA 的分布式系统研究进展
学术加油站|基于 RDMA 的分布式系统研究进展
1023 0
学术加油站|基于 RDMA 的分布式系统研究进展
|
数据采集 数据挖掘 API
3_数据分析—数据清洗及特征处理
3_数据分析—数据清洗及特征处理
556 0
3_数据分析—数据清洗及特征处理
|
弹性计算 安全 Linux
esc使用体验心得
在我看来云服务器有以下优点:省力,不需要专门花时间去维护服务器的硬件,看服务器是否运行正常;稳定,这应该是最主要的有点;安全,做web开发最怕的当然是攻击,所以选择大厂的服务器,自然是最香的;省钱,这当然也是很重要的,尤其对于我们学生用户还是很友好的,爆赞!
|
前端开发 Java Spring
自己实现spring核心功能 一
自己实现spring核心功能 一聊聊spring spring对于java开发者来说,是最熟悉不过的框架了,我们日常开发中每天都在使用它。它有着各种各样的好处,简单易用,得心应手... ... 我们一说到spring就会讲到ioc 、aop、依赖注入,注解等专业名词,不少刚接触java的人,都是一头雾水,很难直观的去理解这些是个什么玩意,但使用的多了 就爱上了它给我们带来的便利。
1092 0