---

DP专题4 不同路径|

原创 已于 2023-09-15 11:56:33 修改 · 粉丝可见 · 175 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132877011

题目：

思路：

根据题意，我们定义一个二维dp，dp 中的 i，j含义就是对应的坐标，dp 是对应坐标的不同路径数量，根据枚举简单数据可以知道。

我们首先要初始化，第一行向右的坐标所对应的不同路径数和 第一列向下的坐标的不同路径数都是 1。因为机器人只能 向右和向下。

随后根据模拟递推可以知道，递推公式是 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

代码详解如下：

int uniquePaths(int m, int n) 
{
	int g[m + 1][n + 1];
	int dp[m + 1][n + 1];
	
	// 初始化 dp
	for(int i = 0;i <= n;++i)
	{
		dp[0][i] = 1;
	}
	for(int i = 0;i <= m;++i)
	{
		dp[i][0] = 1;
	}
	
	// 开始递推公式
	for(int i = 1;i < m;++i)
	{
		for(int j = 1;j < n;++j)
		{
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
		}
	}
	return dp[m - 1][n - 1];
}

最后提交：