首页 > 代码库 > leetcode-unique paths
leetcode-unique paths
代码中的两个方法都是动态规划。
第二种方法很好理解，第一种方法是在第二种方法基础上进行优化，即“降维”，变成一维动态规划。
如soulmachine所写，对于 f[j] = f[j - 1] + f[j];
右边的f[j]，表示老的f[j]，与公式中的f[i-1][j] 对应
左边的f[j]，表示更新后的f[j]，与公式中的f[i[[j] 对应
其实画个3行7列的图自己用纸笔算一下就知道了。等号右边的f[j]代表的其实就是图中上一行的“老”数据，即对应图中当前待更新元素的“上”邻居。而等式右边的f[j-1]其实是在上一轮中刚刚被更新的数据，在图中对应着“左”边的邻居。有了“上”邻居和“左”邻居，数据自然就求出来了。
想不通的时候就拿纸笔“过一遍”，就很清晰了。
除了动态规划外，还可以用别的方法来解答。除了soumachine提供深搜、备忘录之外，还可以看看 http://leetcode.com/2010/11/unique-paths.html
1 #include <iostream> 2 #include <vector> 3 using namespace std; 4 5 class Solution { 6 public: 7 int uniquePaths(int m, int n) { 8 vector<int> a(n,0); 9 a[0] = 1;10 for (int i = 0; i < m; i++)11 { 12 for (int j = 1; j < n; j++)13 {14 a[j] = a[j] + a[j - 1];15 }16 }17 return a[n-1];18 }19 };20 class Solution2 {21 public:22 int uniquePaths(int m, int n) {23 vector<vector<int>> f(m,vector<int>(n,0));24 for (int i = 0; i < m; i++)25 f[i][0] = 1;26 for (int i = 0; i < n; i++)27 f[0][i] = 1;28 for (int i = 1; i < m; i++)29 {30 for (int j = 1; j < n; j++)31 {32 f[i][j] = f[i - 1][j] + f[i][j - 1];33 }34 }35 return f[m - 1][n - 1];36 }37 };38 int main()39 {40 Solution2 s;41 int m = 3;42 int n = 7;43 cout<<s.uniquePaths(m,n)<<endl;44 return 0;45 }
leetcode-unique paths
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。