题解 | #不同路径的数目(一)#

解题思路：

感受到递归 和 动态规划的区别了吗？

相同点：

1、都有边界值，都必须依赖边界值反推

2、有相应的，倒推公式

不同点：

1、动态规划，是一个格一个格填值，倒推结果值

2、递归则是，

import java.util.*;


public class Solution {
    /**
	 * 递归的实现
     * @param m int整型
     * @param n int整型
     * @return int整型
     */
     public int uniquePaths2 (int m, int n) {
         if(m == 1) {
             return 1;
         }
         if(n == 1) {
             return 1;
         }
         return uniquePaths(m-1, n) + uniquePaths(m, n-1);
    }

  	/** 
	 * 动态规划求解
	 */
    public int uniquePaths (int m, int n) {
       int[][] dp = new int[m][n];
       for(int i=0; i<n; i++) {
            dp[0][i] = 1;
       }
       for(int j=0; j<m; j++) {
            dp[j][0] = 1;
       }
       for(int i=1; i<m; i++) {
            for(int j=1; j<n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
       }

       return dp[m-1][n-1];
    }
}