动态规划：求路径

web班张耕

于 2023-01-26 13:20:13 发布

阅读量574

点赞数

分类专栏：蓝桥杯算法题文章标签：动态规划算法深度优先

本文链接：https://blog.csdn.net/qq_55278081/article/details/128764498

版权

蓝桥杯同时被 2 个专栏收录

58 篇文章

订阅专栏

算法题

51 篇文章

订阅专栏

博客介绍了两种求解路径走法的方法。解法一是动态规划，时间复杂度O(m*n)，空间复杂度O(m*n)，通过状态转移方程dp[i][j]=dp[i-1][j]+dp[i][j-1]计算。解法二是组合数学，时间复杂度O(min(m,n))，空间复杂度O(1)，根据从左上角到右下角的步数计算走法。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

解法一：动态规划，时间复杂度：O(m*n) 空间复杂度：O(m*n)

不难发现，如果想到达(i,j)，需要从(i-1,j)向下移动一格或者从(i,j-1)向右移动一格，因此到大(i,j)处的走法dp[i][j]=dp[i-1][j]+dp[i][j-1]。因为到达（i,0）和（0,j）的走法都只有一种（从起点一直横着走或一直竖着走）初始化，因此初始化如下：

代码如下：

int[][] dp=new int[m][n];
for(int i=0;i<m;i++){
    dp[i][0]=0;
}
for(int j=0;j<n;j++){
    dp[0][j]=0;
}

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[i-1][j-1];

解法二：组合数学时间复杂度O(min(m,n)) 空间复杂度：O(1)

由于没有障碍物，因此从左上角到大右下角一共需要走m+n-2步，其中m-1步向下走，n-1步向右走，因此一共有

种走法=（m+n-2)!/(m-1)!*(n-1)!=(m+n-2)*...*n/(m-1)!

代码如下：

int res=1;
for(int x=n,y=1;y<m;y++,x++){
    res=res*x/y;
}
return res;