CCI9.2機器人移動路徑

攝像有個機器人坐在X*Y網(wǎng)的左上角，只能想右、向下移動。機器人從(0,0)到(X,Y)有多少種走法？ 進階 假設有些點為“禁區(qū)”，機器人不能踏足。設計一種算法，找出一條路徑，讓機器人從左上角移動到右下角。 這道題跟LeetCode上的Unique Paths 和Unique Paths I

攝像有個機器人坐在X*Y網(wǎng)格的左上角，只能想右、向下移動。機器人從(0,0)到(X,Y)有多少種走法？

進階

假設有些點為“禁區(qū)”，機器人不能踏足。設計一種算法，找出一條路徑，讓機器人從左上角移動到右下角。

這道題跟LeetCode上的Unique Paths 和Unique Paths II一樣。

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 thr grid(marked 'Finish' in the diagram below).

How many possible unique paths are there?

NOTE: m and n will be at most 100.

Unique Paths II

Follow up for "Unique Paths".

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3*3 grid as illustrated below.

[
 [0,0,0],
 [0,1,0],
 [0,0,0]
]

NOTE: m and n will be at most 100.

解法：

Unique Paths

public int uniquePaths(int m, int n) {
 //這里用了DP解法，因為這種解法可以最大程度避免整數(shù)越界問題
 int[][] memo = new int[m][n];
 for(int i=0; i

Unique Paths II

這里用了一維數(shù)組來代替二維數(shù)組

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
 int m = obstacleGrid.length;
 if(m == 0) return 0;
 int n = obstacleGrid[0].length;
 if(obstacleGrid[0][0] == 1) return 0;
 int[] table = new int[n];
 table[0] = 1;
 for(int i=0; i0)
 table[j] = table[j-1] + table[j];
 }
 }
 return table[n-1];
 }

聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時與本網(wǎng)聯(lián)系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com