有哪些不同路径可以探索？

本文共计748个文字，预计阅读时间需要3分钟。

引言+文本+分享+动态规划算法中比较经典的计数问题，帮助家长简单理解动态规划以及题目特点。+1、问题+给定一个n行m列的矩阵网格，有一个机器人从左上角（0,0）出发，每一步可以向右或向下移动，问有多少种不同的路径到达右下角（n-1,m-1）？+解题思路+动态规划，状态转移方程：dp[i][j]=dp[i-1][j] + dp[i][j-1]，其中dp[i][j]表示到达点(i,j)的路径数。

引言

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

1、问题

给定n行m列的矩阵网格，有一个机器人从左上角(0,0)出发，每一步可以向下或者向右移动一步，求解有多少种不同的方式走到右下角(m-1,n-1)。

2、方法

首先初始化一个二维数组，因为这里是有行和列的矩阵，设nums[i][j]为机器人有多少种方式从左上角走到(i,j)。从(0,0)开始移动，机器人在第一行和第一列向任意方向移动的方式都是1，因此我们可以直接将第一行或是第一列的状态标记为1，其他的所有区域中移动方式均为多种,因此利用状态转移方程求解。