每日一道算法题之不同路径问题
- 一、题目描述
- 二、思路
- 三、C++代码
一、题目描述
题目来源:LeetCode
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
C++程序要求输入输出格式如下:
输入:m n(m为网格行数,n为网格列数)
输出:路径条数
输入:3 7 输出:28
二、思路
根据DP解题步骤:
1.定义一个二维数组来记录路径状态
确定dp数组以及下标的含义:
dp[i][j]:表示从(0,0)出发到达(i,j)有dp[i][j]条不同的路径
2.确定递推公式
从dp[i]的定义可以看出,dp[i] 可以有两个方向推出来。首先想要求dp[i][j],只能有两个方向来推导出来,即dp[i - 1][j] 和 dp[i][j - 1]。
dp[i - 1][j] 表示从(0, 0)的位置到(i - 1, j)有几条路径,dp[i][j - 1]同理。
dp[i][j] = dp[i - 1][j] +