Unique Paths

悠悠 2021-10-23 09:59 291阅读 0赞

class Solution {
    public:
        int uniquePaths(int m, int n) {
            assert(m>=1 && n>=1);
            
            if(m==1 && n==1) return 1;
            if(m<n)
            return help(m+n-2,m-1);
            return help(m+n-2,n-1);
        }
        int help(int m,int n){
            assert(m>0);
            assert(n>=0);
         
            
            if(n==0)return 1;
            
            int **val = new int *[m];
            for(int i=0;i<m;i++)
                val[i] = new int [i+1];
                
            for(int i=0;i<m;i++)
                for(int j=0;j<i+1;j++){
                    cout<<i<<"*"<<j<<" ";
                    if(i==j) val[i][j] = 1;
                    else if(j==0) val[i][j] = i+1;
                    else val[i][j] = val[i-1][j-1] + val[i-1][j];
                }
    
            int res = val[m-1][n-1];
       
            for(int i=0;i<m;i++)
                delete []val[i];
            delete []val;        
            
            return res;
        }
    };

help函数实现的就是 组合问题，C(m,n)

转载于:https://www.cnblogs.com/julie-yang/p/4750209.html

发表评论取消回复

表情：

评论列表（有 0 条评论，291人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 62. Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram

逃离我推掉我的手/ 2022年08月21日 04:13/ 0 赞/ 145 阅读

相关 LeetCode62——Unique Paths

LeetCode62——Unique Paths 《组合数学》一道题。由于有直接的方法，就没怎么思考。答案是从m+n中选出m或者n个结果的组合数，虽然结果是一样的，这里为

短命女/ 2022年08月09日 13:39/ 0 赞/ 163 阅读

相关 Leetcode: Unique Paths

题目： A robot is located at the top-left corner of a m x n grid (marked 'Start' in the d

Love The Way You Lie/ 2022年08月07日 12:45/ 0 赞/ 35 阅读

相关 LeetCode-62. Unique Paths/63. Unique Paths II

62. Unique Paths Problem: > A robot is located at the top-left corner of a m x n gri

怼烎@/ 2022年07月27日 11:57/ 0 赞/ 173 阅读

相关 [Leetcode][python]Unique Paths/Unique Paths II

Unique Paths 题目大意机器人从起点到终点有多少条不同的路径，只能向右或者向下走。解题思路动态规划由于只能有向下向右，只有从\[1\]

左手的ㄟ右手/ 2022年06月07日 07:13/ 0 赞/ 400 阅读

相关动态规划--unique paths 2

1、题目： A robot is located at the top-left corner of a m x n grid (marked 'Start' in the

刺骨的言语ヽ痛彻心扉/ 2022年05月23日 09:09/ 0 赞/ 181 阅读

相关动态规划----unique paths

1、题目： A robot is located at the top-left corner of a m x n grid (marked 'Start' in the

悠悠/ 2022年05月23日 09:04/ 0 赞/ 135 阅读

相关 unique-paths

/\\ \ \ @author gentleKay \ A robot is located at the top-left corner of a m x n g

怼烎@/ 2021年11月09日 08:36/ 0 赞/ 292 阅读

相关 Unique Paths

class Solution { public: int uniquePaths(int m, int n) { ass

悠悠/ 2021年10月23日 09:59/ 0 赞/ 292 阅读

相关 Lintcode: Unique Paths

dp 递推式：dp[i][j] = dp[i-1][j] + dp[i][j-1] 初值：dp[i][j] = 1，i=0 or j=0 空间优化：省掉一维 c...

你的名字/ 2021年04月23日 15:26/ 0 赞/ 346 阅读