不同路径.

devtools/2024/11/24 6:02:55/

本节通过一个求不同路径的实例,再次巩固二维动态规划的基础.

问题描述:

一个机器人位于一个m*n网格的左上角,机器人每次只能向下或者向右移动一步.机器人试图到达网格的右下角,问总共有多少种不同的路径?mhen的值均不超过100.

动态规划算法思路解析:

首先理解题目.机器人每次只能向下或者向右走一步,求起点到终点的路径数.那么当机器人处于某一网格时,要么来自上侧网格,要么来自左侧网格,因此到当前网格的路径数为到上册网格的路径数与到左侧网格的路径之和.由此可见,这是一个有子结构的问题,适合采用动态规划算法.

一般来说,解决这种二维的网格空间问题,需要定义一个二维数组来表示到达的位置是二维网格中的哪一个网格.因此下面来定义一个二维数组:

dp变量:表示一个m*n的二维数组,用于保存到m*n的网格中任意一个的路径数量

该二维数组的初始状态就是第一行和第一列为1.显而易见,想要到达网络的第一行或者第一列都只有一种路径,到达第一行只能向右走,到达第一列只能向下走,因此初始化时,第一行第一列初始化为1,其他位置为0.

完整代码如下:

def uniquePaths(self, m, n):# 初始化一个二维数组dp,用来存储到达每个点的路径数dp = []for i in range(n):  # 遍历列dp.append([0]*n)  # 每一行都初始化为0for i in range(n):  # 再次遍历列dp[i][0] = 1  # 第一列的每个点的路径数为1,因为只能从上面来dp[0] = [1]*m  # 第一行的每个点的路径数为1,因为只能从左边来for i in range(1, n):  # 从第二行开始遍历for j in range(1, m):  # 从第二列开始遍历# 到达dp[i][j]的路径数是上面和左边格子的路径数之和dp[i][j] = dp[i-1][j] + dp[i][j-1]return dp[n-1][m-1]  # 返回右下角格子的路径数,即最终结果


http://www.ppmy.cn/devtools/136472.html

相关文章

03-03、SpringCloud第三章,负载均衡Ribbon和Feign

SpringCloud从看不懂到放弃,第三章 一、Ribbon负载均衡Load Balance 思考 Ribbon、Nginx、Feign 三者有什么区别1、Ribbon简介 1)、Ribbon是一套 【客户端】 的 【负载均衡】 工具2)、负载均衡(Load Balance)分为 集…

自动控制原理 第五章(线性系统的频域分析与校正)(二)

三、对数频率特性(Bode图) 1、典型环节的Bode图 (1)比例环节: (2)微分环节: (3)积分环节: (4)惯性环节: ①…

ARM 架构(Advanced RISC Machine)精简指令集计算机(Reduced Instruction Set Computer)

文章目录 1、ARM 架构ARM 架构的特点ARM 架构的应用ARM 架构的未来发展 2、RISCRISC 的基本概念RISC 的优势RISC 的应用RISC 与 CISC 的对比总结 1、ARM 架构 ARM 架构是一种低功耗、高性能的处理器架构,广泛应用于移动设备、嵌入式系统以及越来越多的服务器和桌面…

4.4 MySQL 触发器(Trigger)

触发器是一种特殊的数据库对象,在特定事件(如INSERT、UPDATE或DELETE)触发时自动执行定义好的操作。它可以帮助我们实现更高效的数据管理和业务规则的约束。 1. 简介 1.1 什么是触发器 触发器(Trigger)是由用户定义的…

react中Fragment的使用场景

在 React 中,Fragment 是一个非常有用的组件,允许你将多个子元素包裹在一起,而不会在 DOM 中产生额外的节点。它通常用于以下几个场景: import React, {Fragment} from react; 1. 返回多个子元素而不添加额外的 DOM 元素&#x…

CSS 设置宽高的单位概览

CSS 设置宽高的单位概览 在 CSS 中,设置宽度和高度的单位有多种,每种单位都有特定的用途和适用场景。下面是常见的单位整理及使用示例。 单位类型代表性单位使用场景视口单位vw, vh响应式布局,全屏背景百分比单位%相对父元素的宽高调整绝对…

自监督学习:从概念到应用的全面解析

引言 自监督学习(Self-Supervised Learning, SSL)是近年来机器学习领域的重要进展,它以未标注数据为核心,通过设计自生成标签的任务,挖掘数据的潜在结构和特征表示。在计算机视觉、自然语言处理(NLP&#…

【一篇搞定配置】网络分析工具WireShark的安装与入门使用

🌈 个人主页:十二月的猫-CSDN博客 🔥 系列专栏: 🏀各种软件安装与配置_十二月的猫的博客-CSDN博客 💪🏻 十二月的寒冬阻挡不了春天的脚步,十二点的黑夜遮蔽不住黎明的曙光 目录 1.…