动态规划真的可以为所欲为的(Leetcode 62/63)

看起来不错的运行效率

62题:

动态规划递推公式: 站在当前方块上可选择的路径数量 = 我正下方那个方块可选择的路径数量 + 我右侧那个方块可选择的路径数量; 边界情况: 棋盘上最右边那列只能选择往下走,所以dp[i][n-1]=1; 棋盘最下面那一行只能选择往右面走,所以dp[m-1][j] = 1; 进一步优化:重复利用一行数组代替m*n的dp数组,节省空间。

class Solution {
public:
    int uniquePaths(int m, int n) {
        int* dp = new int[n];
        memset(dp,0,sizeof(int)*n);
        
        for(int i=m-1;i>=0;i--)
        {
            dp[n-1] = 1;
            for(int j=n-2;j>=0;j--)
            {
                dp[j] = dp[j] + dp[j+1];
            }
        }
        return dp[0];
    }
};
63题:

与62题的不同:凡是放了障碍物的地方dp[i][j]设置成零。如果最右侧一列上任意一个位置有障碍物,那么它以及它正上方的所有方块可选路径为0,也就是dp[i][n-1] = 0;

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(),n;
        if(m>0) n = obstacleGrid[0].size();
        else return 0;
        
        int* dp = new int[n];
        memset(dp,0,sizeof(int)*n);
        
        for(int i=m-1;i>=0;i--)
        {
            if(obstacleGrid[i][n-1]==1||i+1<m&&dp[n-1]==0) dp[n-1] = 0;
            else dp[n-1] = 1;
            for(int j=n-2;j>=0;j--)
            {
                if(obstacleGrid[i][j]==1) dp[j] = 0;
                else  dp[j] = dp[j]+dp[j+1];
            }
        }
        return dp[0];
    }
};

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能

如何在Weka中加载CSV机器学习数据

原文地址:https://machinelearningmastery.com/load-csv-machine-learning-data-weka/

623100
来自专栏GIS讲堂

jquery判断一个div的边界是否超出另外一个div的边界

摘要:本文简单介绍jquery判断一个div的边界是否超出另外一个div的边界,如果超出边界做出相应的处理。

11640
来自专栏AI研习社

如何使用 OpenCV 编写基于 Node.js 命令行界面和神经网络模型的图像分类

如何使用 OpenCV 编写基于 Node.js 命令行界面和神经网络模型的图像分类

23350
来自专栏机器学习实践二三事

Python-OpenCV(2)

这次咱们写个有点意思的东西,上个博客在最后写了画线、画矩形之类的,涉及到取颜色(r g b值),这次咱们就写个图形化的调色板。 具体就是: 三个滑动条分...

30790
来自专栏阿炬.NET

FineUIMvc表格数据库分页,使用CYQ.Data组件

14640
来自专栏非典型技术宅

Quartz2D进行渲染1. 渲染模式2. even-odd rule:奇偶填充规则3. nonzero winding number rule:非零绕数规则4. 其他会用到的渲染模式5. 混合模式

14430
来自专栏ytkah

css自动换行如何设置?url太长会撑开页面

  我们更新文章时如果有引用其他文章一般会带一个原文url,但这个链接如果太长的话会把内容的版块撑开,整个排版乱了。那我们能不能设置css自动换行呢?如下图所示...

30950
来自专栏点滴积累

geotrellis使用(九)使用geotrellis进行栅格渲染

目录 前言 图像渲染 总结 参考链接 一、前言        前面几篇文章讲解了如何使用Geotrellis进行数据处理、瓦片生成等,今天主要表一下如何使用Ge...

37850
来自专栏木头编程 - moTzxx

PHP 自定义图片的生成与保存实例讲解

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

33630
来自专栏阿炬.NET

FineUIMvc表格数据库分页,使用CYQ.Data组件

42380

扫码关注云+社区

领取腾讯云代金券