动态规划---到原点的路径

时间：2021-09-23 19:58:38 收藏：0 阅读：24

题目：在平面坐标的p(n,m)点，向原点(0,0)走去，每次一步，只能向左或向下走，请问路径数目？

分析：

令在任意点p的数目为f(n,m)，则f(n,m)=f(n-1,m)+f(n,m-1)
在轴上的坐标都是1条路径到原点（dp和递归边界的处理）
关键是这题的边界条件：对于边界一般从(0,0)开始考虑，但这题是在轴上！！！

方法一：递归写法

1 int f(n,m)
2 {
3     if(n==0||m==0)
4         return 1;
5     else 
6         reurn f(n-1,m)+f(n,m-1);
7 }

方法二：动态规划写法

 1 int f(n,m)
 2 {
 3     int dp[n+1][m+1];
 4     
 5     for(int i=0;i<=n;i++)
 6     {
 7         dp[i][0]=1; 
 8     }
 9     for(int j=0;i<=m;j++)
10     {
11         dp[0][j]=1;
12     }
13     
14     for(int i=1;i<=n;i++)
15     {
16         for(int j=1;j<=m;j++)
17         {
18             dp[i][j]=dp[i-1][j]+dp[i][j-1];
19         }
20     }
21     
22     return dp[n][m];
23 }

方法三：组合数解法（待加

链接：https://www.geeksforgeeks.org/counts-paths-point-reach-origin/

原文：https://www.cnblogs.com/cwfeng/p/15311919.html