Unique Paths, Leetcode 解题笔记

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?

robot_maze

一维的动态规划题,利用一维数组可以简单的解决。
数组中的元素存储到达当前位置的unique path数,然后逐行更新。更新的公式为A[index] = A[index] + A[index-1]。即此位置的上方和左边的位置里存的数字加合。

public class Solution {
    public int uniquePaths(int m, int n) {
        int[] store = new int[n];
        Arrays.fill(store, 1);
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                store[j] = store[j] + store[j-1];
            }
        }
        return store[n-1];
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s