294-机器人路径

浅浅的花香味﹌ 2023-01-16 06:54 93阅读 0赞

## 机器人路径 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]

**我们可以走的路径可以是**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]

## 如何表示走的路径数？ ##

**首先建立动态方程式：  
我们假设**  
![在这里插入图片描述][20210424201525409.png_pic_center]  
**i代表行，j代表列，dp \[i\]\[j\]代表总的路径数。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]

vector<vector<int> > dp(m, vector<int>(n, 0));

代表的是下图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]

## 解题代码 ##

#include<iostream>
    #include<vector>
    using namespace std;
    
    int uniquePath(int m, int n)
    {
        
    	if (m <= 1 || n <= 1) return 1;
    	vector<vector<int> > dp(m, vector<int>(n, 0));
    	for (int i = 0; i < m; ++i)//行数 
    	{
        
    		dp[i][0] = 1;
    	}
    	for (int j = 0; j < n; ++j)//列数 
    	{
        
    		dp[0][j] = 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];
    
    }
    int main()
    {
        
    	int m, n;
    	cin >> m >> n;
    	cout << uniquePath(m, n) << endl;
    }

## 运行程序 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 4]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/2a42767895b045a5b4c345fffc359ac4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/4ad1f578747c4d6d904eaf21cecd8332.png
[20210424201525409.png_pic_center]: /images/20221022/5356cd3c29db448aa5e3a6785ddbc44d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221022/0c2a6fd685444417bb4bc89832608fad.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221022/031faaf333d246b49f1c3f7eef75f28f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221022/6091a7542dfd4caa8ab49adb1b2d2c73.png