不同路径(动态规划)- leetcode 62

最近在看leetcode的题目,都是面试题,需要面试的同学可以努力刷这里的题目,因为很多公司的面试笔试题都是参考这个上面的。相对OJ上的题目,感觉要简单一些。

OK,来看题目。

题目描述:

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。

问总共有多少条不同的路径?

说明:mn 的值均不超过 100。

示例 1:

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例 2:

输入: m = 7, n = 3
输出: 28

解题思路:

采用DP的方式思考这道题,dp(i,j)表示从起点(0,0)到点(i,j)的路径数。注意这个dp用的是逆向,从dp(m,n)开始。

对于任意的dp(i,j)存在dp(i,j) = dp(i-1, j) + dp(i, j-1)这个转换公式。这是本dp解法的核心。

我的代码:0ms

#define printf //printf

int * c = 0;
int M = 0;

int dp(int i, int j)
{
    if (i <= 0 || j <= 0) {
        return 0;
    }

    if (i == 1 && j == 1) {
        return 1;
    }

    int s = (j - 1) * M + i;
    if (c[s] > 0) {
        printf("c[%d] => %d\n", s, c[s]);
        return c[s];
    }

    int u = dp(i, j - 1);
    int l = dp(i - 1, j);
    c[s] = u + l;
    printf("c[%d] = %d\n", s, c[s]);
    return u + l;
}

int uniquePaths(int m, int n) {
    M = m;
    int t = m * n + 1;
    c = malloc(sizeof(int) * t);
    memset(c, 0, sizeof(int)*t);
    return dp(m, n);
}

int main()
{
    printf("%d\n", uniquePaths(7, 3));
    return 0;
}

官方最优代码:0ms

int uniquePaths(int m, int n) {
    int ways[m][n];
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(i==0 || j==0){
                ways[i][j]=1;
            }else{
                ways[i][j]=ways[i][j-1]+ways[i-1][j];
            }
        }

    }
    return ways[m-1][n-1];

}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-06-21

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏SimpleAI

Hello,1024背后可爱的人儿

14940
来自专栏祝威廉

从DataFrame自动化特征抽取的尝试

虽然提供了很多Estimator/Transformer, 正如这篇文章所显示的,如何基于SDL+TensorFlow/SK-Learn开发NLP程序,处理的代...

8930
来自专栏算法修养

矩阵快速幂小结

      矩阵快速幂大概是用来解决这样一类问题,当你知道了一个递推式比如a[n]=a[n-1]+a[n-2] 题目要求你求出a[n]。如果n大于1亿怎么办? ...

32650
来自专栏深度学习自然语言处理

【笔记】高效率但却没用过的一些numpy函数

最近在看源码的时候,碰到了一些大佬们常用,但自己暂时还没用过的numpy函数,特意来总结下。

7320
来自专栏沈唁志

PHP使用递归算法查找子集获取无限极分类等实操

递归函数是我们常用到的一类函数,最基本的特点是在函数或子过程的内部,直接或者间接地调用自己的算法,但必须在调用自身前有条件判断,否则无限调用下去,也就是所谓的死...

26130
来自专栏Pytorch实践

python实现字符串模糊匹配

之前笔者写过一篇文章关于如何做搜索,但那篇文章的角度是从文本相似度角度写的。那种方式是目前发展的趋势,但是真正的搜索特别是网页搜索不可能在大范围的文本之间两两算...

4.1K60
来自专栏数据结构与算法

深海中的STL—mt19937

mt19937 当你第一眼看到这玩意儿的时候 肯定禁不住吐槽:纳尼?这是什么鬼? 确实,这个东西鲜为人知,但是它却有着卓越的性能 简介 mt19937是c++1...

31740
来自专栏数据小魔方

sparklines迷你图系列15——Composition(BoxPlot)

今天要跟大家分享的是sparklines迷你图系列14——BoxPlot。 箱线图是用于呈现数据分布形态(功能类似直方图)的一种图表,对于连续型数据,箱线图可以...

30840
来自专栏Petrichor的专栏

深度学习: global pooling (全局池化)

今天看SPPNet论文时,看到“global pooling”一词,不是很明白是啥概念。上网查了一下定义,在StackOverflow 上找到了答案:

50630
来自专栏C语言C++游戏编程

400行代码编C语言控制台界版2048游戏,编写疯子一样的C语言代码

《2048》是最近比较流行的一款数字游戏。原版2048首先在github上发布,原作者是Gabriele Cirulli。它是基于《1024》和《小3传奇》(T...

16700

扫码关注云+社区

领取腾讯云代金券