[LintCode/LeetCode] Unique Paths
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
Note
간단 한 동 규 문제, dp 배열 을 만 듭 니 다.
dp[i][j] 좌 표 는 행렬 의 좌표 이 고 값 은 왼쪽 상단 에서 이 칸 까지 의 주 법 총수 이다.초기 값 을 부여 합 니 다. 맨 위 줄 과 맨 왼쪽 열 에 있 는 모든 칸 의 주 법 은 한 가지 만 있 고 나머지 칸 의 주 법 은 왼쪽 칸 의 주 법 과 위 칸 의 주 법 과 같 습 니 다.마지막 으로 돌아 가면 된다 dp[m-1][n-1].Solution
2 차원 DP
public class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0) dp[i][j] = 1;
else dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}1 차원 DP
public class Solution {
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] += dp[j-1];
}
}
return dp[n-1];
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
CSS 그리드로 2차원 레이아웃 구축이 기사를 쓰기 전에 나는 1D 레이아웃을 행 또는 열로 만들고 더 구체적으로 다음과 같이 그리드 내부의 요소에 고정 크기를 제공하기 위해 CSS Grid를 사용했습니다. 한 번에 훌륭한 2D 레이아웃을 만드는 데 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
