动态规划(4)-求路径

求路径

https://www.nowcoder.com/practice/166eaff8439d4cd898e3ba933fbc6358?tpId=117&tqId=37736&rp=1&ru=%2Fta%2Fjob-code-high&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey

题目描述

一个机器人在m×n大小的地图的左上角(起点)。
机器人每次向下或向右移动。机器人要到达地图的右下角(终点)。
可以有多少种不同的路径从起点走到终点?

示例

输入
2,1
返回值
1

思路

  1. Q1:dp数组如何设置?二维数组中求一条路径,一般设置dp为二维数组。dp[i][j]表示到达ij位置的结果。

    code

    import java.util.*;
    public class Solution {
     public int uniquePaths (int m, int n) {
         if(m<=0 || n<=0)return 0;
         int[][] dp = new int[m][n];
         for(int i=0;i<m;i++)dp[i][0]=1;
         for(int i=0;i<n;i++)dp[0][i]=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];
     }
    }
全部评论

相关推荐

10-15 15:00
潍坊学院 golang
跨考小白:这又不是官方
投递拼多多集团-PDD等公司10个岗位
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务