62. 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.

我的答案:

    public static int uniquePaths(int m, int n) {
        int top = 1;
        int left = 1;
        return pathSum(top,left,m,n);
    }
    public static int pathSum(int top,int left,int m,int n){
        if( left == m && top == n){
            return 1;
        }else if(top==n){
        return pathSum(top,left+1,m,n);
        }else if( left == m){
            return pathSum(top+1,left,m,n);
        }else if( left < m && top < n){
            return pathSum(top+1,left,m,n)+ pathSum(top,left+1,m,n);
        } 
        return 0;
     }

大神答案:

1.简化版的递归
     public int uniquePaths(int m, int n) {
        return uniquePaths(1,1,m, n);
    }
    
    public int uniquePaths(int currentRow, int currentColumn, int m, int n){
        if(currentRow==m || currentColumn==n){
            return 1;
        }    
        return uniquePaths(currentRow+1, currentColumn, m ,n ) + uniquePaths(currentRow,                    currentColumn+1, m, n);
    }

2.利用杨辉三角求解:
在Dynamic Programming思路的指引下,我们可以尝试将递归的方法改变为循环的方法来解决。这里就运用到了数学中的杨辉三角。很显然,最左侧一行和最顶侧一行的到达路径数都是1,而任何一个非该行列的节点都可以通过左侧节点和上侧节点的路径数相加得到从起点出发到达自己共有的路径数。我们可以利用二维数组来实现叠加。代码如下:
    public static int pathSum(int top,int left,int m,int n){
        int[][] a = new int[m][n];
        
        for (int i = 0; i < m; i++) {
            a[i][0] = 1;
        }
        
        for (int i = 0; i < n; i++) {
            a[0][i]=1;
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                a[i][j] = a[i][j-1]+a[i-1][j];
            }
        }
        return a[m-1][n-1];
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 268. Missing Number

    Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find th...

    luozhiyun
  • 219. Contains Duplicate II

    Given an array of integers and an integer k, find out whether there are two dist...

    luozhiyun
  • 605. Can Place Flowers

    Suppose you have a long flowerbed in which some of the plots are planted and som...

    luozhiyun
  • BZOJ3498: PA2009 Cakes(三元环)

    如果\(v\)的度数\(\leqslant M\),那么就再暴力枚举\(v\)连出去的点\(t\),看\(u\)与\(t\)是否联通(打标记)

    attack
  • 洛谷P2831 愤怒的小鸟(状压dp)

    直接状压dp一下,\(f[sta]\)表示干掉\(sta\)这个集合里面的鸟的最小操作数

    attack
  • Java经典编程50题(面试笔试机试)

    https://blog.csdn.net/alias_fa/article/details/52985112

    林万程
  • 挑战程序竞赛系列(8):2.1一往直前!贪心法(其他)

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • C语言——小学题目B卷解析(终)

    第6题,简单说明:系统有默认的转化规则,就是从精度底的转化为精度高的,避免计算时精度的丢失。coding一下:

    Ed_Frey
  • 【BZOJ 1701】Cow School(斜率优化/动态凸包/分治优化)

    小牛参加了n个测试,第i个测试满分是??pi,它的得分是??ti。老师去掉??/??ti/pi最小的d个测试,将剩下的总得分/总满分作为小牛的得分。小牛想知道多...

    饶文津
  • HBU-DS2018SY-1-1 数组循环左移 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk

扫码关注云+社区

领取腾讯云代金券