本文共 2063 字，大约阅读时间需要 6 分钟。
采用动态规划（DP）求解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.
问题分析
这个题目是从一个3*7的矩阵（方格）中，找出从左上角到右下角的所有可能路径。每次在方格矩阵中移动位置时，只能向右或者向下移动。
左上角的位置记为 [0，0]，只有一行时，移动的位置可以表示为：[0,i] （i = 0..i）；只有一列时，移动的位置可以表示为：[j,0] （j = 0..j）
当从第 [i,j] 位置开始移动时，其下一个位置只能向右，或者只能向下；则位置可以表示为：[i+1,j]，或者 [i,j+1]；反过来想想，从第 [i,j] 位置反推来时的位置，要么是从上面的格子走过来的，上面的格子坐标可以表示为：[i,j-1]；要么是从左边的格子走过来的，左边的格子坐标可以表示为：[i-1,j]。
我们假设给第1行和第1列的格子赋初值均为 1。为什么第1行的格子和第1列的格子都赋值1呢？如下图所示：
因为从（0，0）向右移动到（0，1）位置只有唯一的一种走法；从（0，0）移动到（1，0）也只有唯一的一种走法。
反过来想，如果机器人现在在（2，0）位置，那么从上一个位置（1，0）到当前位置（2，0）也只有唯一的一种走法。 所以，第1行的任何一个格子，或者第1列的任何一个格子，都可以被标记为1。（因为只有1种走法）但是如果从（0，0）位置移动到（1，1）位置呢？ 有两条路径：
第1条：（0，0）移动到（0，1），再移动到（1，1） 第2条：（0，0）移动到（1，0），再移动到（1，1） 那么位置（1，1）的值可以标记为2。余此类推，除第一行，第一列的所有格子之外，单元格的值可以表示有几条路径可以达到该单元格。
好了，至此，问题从对于一个M*N的矩阵，从左上角（0，0）移动到右下角（m，n）时有多少条不同的路径，可以转化为从（m-1，n-1）移动到（m，n）有几条不同的路径。
状态转移方程为： dp（m，n）= dp（m-1，n）+dp（m，n-1）
算法设计
package com.bean.algorithmbasic;public class UniquePathsDemo { /* * ｍ和ｎ最大不超100。 * */ public static int uniquePaths(int m, int n) { int[][] result = new int[m][n]; // 第一列的解 for (int i = 0; i < m; i++) { result[i][0] = 1; } // 第一行的解 for (int i = 1; i < n; i++) { result[0][i] = 1; } // 其它位置的解 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { result[i][j] = result[i - 1][j] + result[i][j - 1]; } } // 所求的解 return result[m - 1][n - 1]; } public static void main(String[] args) { // TODO Auto-generated method stub int result = uniquePaths(3, 7); System.out.println("RESULT IS: " + result); }} 计算结果为：
RESULT IS: 28
（完）