LeetCode 62. Unique Paths

原题：https://leetcode.com/problems/unique-paths/
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.

思路

这是个经典的题目，反正就是动态规划的思路？说是动态规划，其实就是下一个状态怎么来的问题。此处的下一状态就是一个格子solution[m][n]他的结果是怎么来的问题，由于限定只能往右或者往下走，所以这个格子的走法无非是 从(m,n-1)和(m-1,n)走过来两种，只要把这两个状态的结果相加就是当前总的走法了。

解法

复杂度应该是O(m*n)，做的时候在左侧和上侧加了个0边便于计算

public class Solution {
    public int uniquePaths(int m, int n) {
        int solutions[][] = new int[m+1][n+1];
        solutions[1][1]=1;
        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                if(i==1 && j==1)
                    continue;
                solutions[i][j] = solutions[i][j-1] + solutions[i-1][j];    // Comes from left, or upper side
            }
        }
        return solutions[m][n];
    }
}