动态规划(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
思路
- 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]; } }
查看8道真题和解析
