# Unique Paths - tags: [[DP_Matrix](# "根據動態規劃解題的四要素，矩陣類動態規劃問題通常可用 f[x][y] 表示從起點走到坐標(x,y)的值")] ### Source - lintcode: [(114) Unique Paths](http://www.lintcode.com/en/problem/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? Note m and n will be at most 100. ~~~ ### 題解 題目要求：給定*m x n*矩陣，求左上角到右下角的路徑總數，每次只能向左或者向右前進。按照動態規劃中矩陣類問題的通用方法： 1. State: f[m][n] 從起點到坐標(m,n)的路徑數目 1. Function: f[m][n] = f[m-1][n] + f[m][n-1] 分析終點與左邊及右邊節點的路徑數，發現從左邊或者右邊到達終點的路徑一定不會重合，相加即為唯一的路徑總數 1. Initialization: f[i][j] = 1, 到矩陣中任一節點均至少有一條路徑，其實關鍵之處在于給第0行和第0列初始化，免去了單獨遍歷第0行和第0列進行初始化 1. Answer: f[m - 1][n - 1] ### C++ ~~~ class Solution { public: /** * @param n, m: positive integer (1 <= n ,m <= 100) * @return an integer */ int uniquePaths(int m, int n) { if (m < 1 || n < 1) { return 0; } vector<vector<int> > ret(m, vector<int>(n, 1)); for (int i = 1; i != m; ++i) { for (int j = 1; j != n; ++j) { ret[i][j] = ret[i - 1][j] + ret[i][j - 1]; } } return ret[m - 1][n - 1]; } }; ~~~ ### 源碼分析 1. 異常處理，雖然題目有保證為正整數，但還是判斷一下以防萬一 1. 初始化二維矩陣，值均為1 1. 按照轉移矩陣函數進行累加 1. 任何`ret[m - 1][n - 1]`