LetCode-62-Unique Paths*(동적 계획)

1723 단어 array
Unique Paths
 
에서https://leetcode.com/problems/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?
 
Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
제목 해석:
한 로봇이 2차원 mxn 격자의 가장 왼쪽 위에 있다(아래의 예에서'Start'라고 표시한다).이 로봇은 오른쪽이나 아래로만 이동할 수 있으며 2차원 격자의 가장 오른쪽 아래에 도달하려고 한다(아래의 예에서'Finish'라고 표시한다).
모두 몇 가지 다른 경로가 있습니까?
 
Note:
m와 n은 최대 100이다.
 
해결:
이것은 임의의 격자를 최종 목적지로 삼으면 동적 기획의 문제이다.그 위치에 도달하는 서로 다른 경로 종수는 그 위와 왼쪽의 서로 다른 경로 종수의 합이다.
 
 
Java 코드:
public class Solution {
    	//    
	public int uniquePaths(int m, int n) {
		if(0==m || 0==n) 
			return 0;
		//           
		if(1==m && 1==n)
			return 1;
		
		int[][] dynamicPlanning = new int[m][n];
		
		//          1,                      
		for(int i=0; i<m; i++)
			dynamicPlanning[i][0] = 1;
		//        1,                     
		for(int i=0; i<n; i++)
			dynamicPlanning[0][i] = 1;
		
		for(int i=1; i<m; i++) {
			for(int j=1; j<n; j++) 
				//                           
				dynamicPlanning[i][j] = dynamicPlanning[i-1][j] + dynamicPlanning[i][j-1];
		}
		return dynamicPlanning[m-1][n-1];
	}
}

 
알고리즘 라인 기능:

좋은 웹페이지 즐겨찾기