算法:动态规划(DP)入门实践

入门

在知乎上看到徐凯强 Andy的答案后感觉入门了

实践

题目:仅包含0/1的矩阵,求其中最大的全1方阵(不能是矩形)的边长

题解:matrxi[100][100]表示0/1矩阵,dp[i][j]表示:以matrix[i][j]为右下角,边长最大为min(i,j)的,最大全1方阵的边长, if(matrix[i][j]==0) { dp[i][j]=0; } if(matrix[i][j]==1) { if(dp[i-1][j]==1&&dp[i][j-1]==1) { dp[i][j]=dp[i-1][j-1]+1; } else { dp[i][j]=1; } } 最后dp数组中最大的值即所求的边长

题目:https://leetcode.com/problems/trapping-rain-water/description/ Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

题解:https://leetcode.com/problems/trapping-rain-water/solution/ 核心思想:维护一个区间,当区间缩小时看看是否有一边下降,如果下降则盛雨量增加,否则向内移动短边。

 // https://leetcode.com/problems/trapping-rain-water/solution/
 // Approach #4 Using 2 pointers [Accepted]
 int trap(vector<int>& height)
{
    int left = 0, right = height.size() - 1;
    int ans = 0;
    int left_max = 0, right_max = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            height[left] >= left_max ? (left_max = height[left]) : ans += (left_max - height[left]);
            ++left;
        }
        else {
            height[right] >= right_max ? (right_max = height[right]) : ans += (right_max - height[right]);
            --right;
        }
    }
    return ans;
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏张泽旭的专栏

java计算奇数阶魔方阵

所谓“奇数阶魔方阵”是指n为不小于3的奇数的魔方阵。这类魔方阵的形式多样,这里我们仅讨论其中的一种形式的正规魔方阵。例如:3阶、5阶和7阶的魔方阵如图3 – 4...

12720
来自专栏智能算法

自动还原魔方算法数据结构

来自:CSDN博客 作者:寸辰 链接:http://blog.csdn.net/cun_chen/article/details/50261787(点击尾部阅读...

34850
来自专栏数据结构与算法

HDU 3480 Division

Problem Description Little D is really interested in the theorem of sets recen...

27890
来自专栏desperate633

LintCode 矩阵的之字型遍历题目分析代码

给你一个包含 m x n 个元素的矩阵 (m 行, n 列), 求该矩阵的之字型遍历。

8110
来自专栏Bingo的深度学习杂货店

Q172 Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!. Note: Your solut...

33550
来自专栏菩提树下的杨过

“AS3.0高级动画编程”学习:第四章 寻路(AStar/A星/A*)算法 (中)

上一部分提到了节点(Node),代价(Cost),估价公式等基本概念,有了这些知识铺垫 就可以正式开启寻路之旅了! ? 如上图,这是一个5行8列的网格,黄色节点...

27360
来自专栏软件开发 -- 分享 互助 成长

C++中巧妙的位运算

位运算要多想到与预算和异或运算,并常常将两个数对应位上相同和不同分开处理 一、x&(x-1)消除x二进制中最右边的一个1。 这个比较厉害,比如统计某个 二、与和...

36060
来自专栏Spark学习技巧

CountVectorizer

CountVectorizer 关于文本特征提取,前面一篇文章TF-IDF介绍了HashingTF,本文将再介绍一种Spark MLlib的API CountV...

70070
来自专栏章鱼的慢慢技术路

Direct3D 11 Tutorial 3: Shaders and Effect System_Direct3D 11 教程3:着色器和效果系统

在上一个教程中,我们设置了一个顶点缓冲区并将一个三角形传递给GPU。 现在,我们将逐步完成图形管道并查看每个阶段的工作原理。 将解释着色器和效果系统的概念。

9510
来自专栏数据结构与算法

洛谷 P3807 【模板】卢卡斯定理

题目背景 这是一道模板题。 题目描述 给定 求  保证P为prime C表示组合数。 一个测试点内包含多组数据。 输入输出格式 输入格式: 第一行一...

28040

扫码关注云+社区

领取腾讯云代金券