动态规划:括号知多少

主要推送关于对算法的思考以及应用的消息。培养思维能力,注重过程,挖掘背后的原理,刨根问底。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。

01

你会学到什么?

在上一消息推送中,我们通过《装水最多的容器》这个实际问题,初步了解了动态规划的魅力所在,还记得如果我们枚举所有可能的容器高度和边长时得到算法时间复杂度很大,而经过仔细分析目标函数和其变量关系时,我们发现把初始值设置为最大底边长度乘以相对小的高度后,之后的迭代中最大面积的容器只可能出现在尽可能高的情况下,如下动画所示,初始值为12,然后动态地交替地调整两个边(指针),目的是牺牲底的长度,尽量获得大的容器高度,从而得到更大的容器,果然在索引为2,和5时,容器的最大高度为 24 。

在本推送中,我们继续体验动态规划这个算法思想,领域经过仔细分析思考后的算法性能的优越,往往直观的第一下想到的算法不是很优秀的算法,当然排除那些大牛,毕竟他们已经形成了优秀算法的思维,这是我们努力的方向。

02

讨论的问题是什么?

讨论动态规划思想到底该怎么应用到实际问题当中。怎么拿到一个问题,然后就能想到用动态规划区解决呢?

这次探讨的这个实际问题,比较有意思,是给出一堆括号,让你分析出最长的括号长度,当然是辨识出有效的括号长度。

03

实际问题描述

先看原题,摘自LeetCode官网:

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. For "(()", the longest valid parentheses substring is "()", which has length = 2. Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

题目的意思是求出有效括号的长度的最大值,举了几个例子:

  1. (() 有效长度为2
  2. )()()) 有效长度为4
  3. ((()()()) 有效长度为8

初步分析

看到这个问题,首先要想一个问题,给定一个字符串,怎么判断这个字符串是否是有效的字符串括号呢?

借助栈,如果是 ( 将之推到栈中,如果是 ) ,判断栈顶是 ( 吗,如果是,则表明找到一对有效的组合并出栈 (;如果不是,说明这个不是有效字符括号串,或者栈为空了,进来一个 ),也表明不是有效的字符串。

找到判断一个字符串是否是有效的方法后,当然可以穷举这个字符串括号的所有子字符串,这个过程就得 O(n^2) 的时间复杂度,大家可以想下,这个算法肯定不是高效的。

那么,有没有更好的算法呢?

04

括号知多少

大家想下上面的那个判断一个括号串的算法,会不会有更简单的实现。

有的。如果一个括号串的结尾是 (,那么这个括号串一定不是有效的串;

所以,有效的括号串一定得以 ) 结尾才行。

因此,我们定义一个数组 dp[n] ,n为字符个数。 dp[i]表示的含义:以索引i结尾的子字符串的最长长度。

因为上文提到过,有效字符串一定得以 ) 结尾,并且先研究两个连续相邻的字符(至于为什么,请看下面的具体讨论),所以我们只需要讨论两种情况,即

  1. ()
  2. ))

具体说来如下,

如果 str[i] = ')',并且 str[i-1] = '(',比如 ...()(),在这种情况下的状态转换方程为

dp[i] = dp[i-2] + 2

如果 str[i] = ')',并且 str[i-1] = ')',比如 ...)),

如果再满足 str[ i - dp[i-1] - 1] = '(',比如 .....(()()),这种情况的状态转化方程为

dp[i] = dp[i-1] + 2 + dp[ i- dp[i-1] -2]

这种情况不是很好理解,请参考下图理解,可以看到 索引 i 此时等于 7,

dp[7] = dp[6] + 2 + dp[7 - dp[6] - 2]

至此这个问题,借助动态规划的思想,通过找到状态的转移方程,我们便找到了问题的解,这个问题的转化公式由以上两种情况组成。

05

源码实现

有了以上的分析和动态转移方程,代码便出来了,如下所示:

public int longestValid(String s){
  int maxlen = 0;
  int dp[] = new int[s.length()];
  for(int i=1; i<s.length();i++){
  if(s.charAt(i)==')'){ //这是第一个大条件
 //情况1
  if(s.charAt(i-1)=='('){
  dp[i] = (i>=2? dp[i-2]:0)+2;
  }//情况2
  else if(i-dp[i-1]>0 && 
  s.charAt(i-dp[i-1]-1)=='('){
  int tmp = i-dp[i-1]>=2? 
  dp[i-dp[i-1]-2]:0+2;
  dp[i] = dp[i-1] + 2 + tmp;
  }
  maxlen = Math.max(maxlen, dp[i]); 
  }
  }
  return maxlen;
  }

06

总结

以上动态规划算法的时间复杂度为 O(n),空间复杂度为 O(n) 。算法通过分析得出满足一定条件下的两个不同的状态转移方程,然后动态的求出子字符串的最大有效括号长度,这便是动态规划的思想之所在。

以上算法思想部分参考LeetCode。

07

GitChat

这是我发起的一次Chat,诚邀您的参与!

最常用的 8 个排序算法:从原理到改进,再到代码兑现透彻解析

越到最后,你越会明白算法和数据结构很 cool,很 essential。这些都是内功,和用什么语言、技术或框架无关。本场 Chat 的主要内容包括:

  • 8 个主要排序算法的思想和原理图解,代码兑现
  • 从冒泡排序到快速排序做的那些优化
  • 从直接选择排序到堆排序做的那些改进
  • 从直接插入排序到希尔排序做的那些改进
  • 归并排序算法的过程图解
  • 不基于比较的基数排序原理图解

原文发布于微信公众号 - 算法channel(alg-channel)

原文发表时间:2017-11-04

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C语言及其他语言

[每日一题]矩阵问题

今天给大家分享的是二维数组的基本用法,主要是利用数组对行列的控制 题目描述 求一个3×3矩阵对角线元素之和。 输入 矩阵 输出 主对角线 副对角线 元素和 ...

3287
来自专栏大数据文摘

正则表达式太慢?这里有一个提速100倍的方案(附代码)

2464
来自专栏数说工作室

1. PRXMATCH () | 提取文本数据,分析师小王初上手!

【SAS Says·扩展篇】分析师小王初上手! | 1. PRXMATCH () 本集目录: 0. 小王初上手 1. 初始PRXMATCH() 2. metac...

3366
来自专栏专知

​关关的刷题日记100 – Leetcode 442. Find All Duplicates in an Array

关关的刷题日记100 – Leetcode 442. Find All Duplicates in an Array 题目 Given an array of ...

3546
来自专栏七夜安全博客

从多项式相加看线性结构

1363
来自专栏人工智能头条

Python 再牛,在字符串排序上还是被 Julia 和 R 碾压

在《实例对比 Julia, R, Python,谁是狼语言?》我们简单介绍了 Julia 的背景,以及通过优化一个似然函数的参数 μ 和 σ,来对比 Julia...

1323
来自专栏python读书笔记

《算法图解》NOTE 4 快速排序法1.递归与分治法2.快速排序法的实现3.快速排序法的时间复杂度(用渐近表示法表示)

2106
来自专栏Vamei实验室

纸上谈兵: 排序算法简介及其C实现

排序的目标是将一组数据 (即一个序列) 重新排列,排列后的数据符合从大到小 (或者从小到大) 的次序。这是古老但依然富有挑战的问题。Donald Knuth的经...

2529
来自专栏追不上乌龟的兔子

[多少懂点位运算]找出唯一的数字

大家都知道现代计算机的底层是以二进制为基础的,计算机所有的操作最后都归结到了简单的二进制位运算上:与,或,非和异或。

2565
来自专栏chenjx85的技术专栏

leetcode-169-Majority Element

2134

扫码关注云+社区

领取腾讯云代金券