首页 > 代码库 > leetcode Unique Paths
leetcode Unique Paths
题目：给定一个m*n的矩阵，从头开始，只能往右边和下边走，一次走一格，知道走到最后一个（右下角）为止。总共有多少种走法。
典型的动态规划吧。其实从头走到尾部，和从尾部开始走到头是一样的次数。我们用一个矩阵记录到第一格子的次数，那么可以看到有如下的表：
假设是3*4的矩阵，那么我们要返回的就是10了，每个当前的值是它的左边加上上边
代码如下：
class Solution {public: int uniquePaths(int m, int n) { vector<vector<int> > ans(m, vector<int>(n)); for (int i = 0; i < m; ++i) { ans[i][0] = 1; } for (int j = 0; j < n; ++j) { ans[0][j] = 1; } for(int i = 1; i < m; ++i) for (int j = 1; j < n; ++j) { ans[i][j] = ans[i-1][j] + ans[i][j-1]; } return ans[m-1][n-1]; }};
leetcode Unique Paths
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。