【肝了好多天!】-动态规划十连-超细腻解析——《我的Java打怪日记》-阿里云开发者社区

开发者社区> 开发与运维> 正文
登录阅读全文

【肝了好多天!】-动态规划十连-超细腻解析——《我的Java打怪日记》

简介: 周末肝了几道动态规划题,写一下我的心得笔记,故事开头,文章循序渐进,如果看官出现头疼不适,望休息,但是别放弃一定要看完!号外:每道题都有单元测试,看官们直接copy就可以debug了。

\>【刷题打卡】周末肝了几道动态规划题,写一下我的心得笔记,故事开头,文章循序渐进,如果看官出现头疼不适,望休息,但是别放弃一定要看完!号外:每道题都有单元测试,看官们直接copy就可以debug了。

No.1

\### 最简单的动态规划题目

侄女5岁现在开始学习加减法了,每次做数学都离不开她的小手指,超过5的就开始数另一个手的手指,真是汗颜啊

有一天,我问她

“1+1+1+1+1等于多少?”

“搬起小拇指,就开始数了,5!”

“那么再加一个1呢?”

“当然是6了” -脱口而出

“这次你怎么算这么快的?”

“刚刚不是5吗,加1就是6了啊”

“所以你不需要重新计算,因为你记得之前的答案是5!动态规划就是说:记住之前的东西可以节省时间”

color{red}{玩归玩,闹归闹,别拿dp开玩笑!

来瞅一眼科普中国科学百科的词条解释

动态规划(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程最优化的过程。20世纪50年代初,美国数学家贝尔曼(R.Bellman)等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,从而创立了动态规划。动态规划的应用极其广泛,包括工程技术、经济、工业生产、军事以及自动化控制等领域,并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。

看不完的童鞋跳过,咱整点简单点的

其实刚刚这道题应该算是最简单的动态规划题目了。

我们可以看出这道题有什么特点呢?

我们知道之所以最后一步加1会计算的那么快,大部分要归功于之前计算过答案是5,如果我们把问题归纳为一个子问题,我想要计算每一步的答案,就可以列出一个方程:f(x) = f(x -1) + 1, 大家别对f(x)发怵,就把它当做一个简单的方法。

其中,f(x)为第几步的值,设定一个初始值,x > 0, 则第一步

f(1) = 1;

f(2) = f(1) + 1;

...

f(6) = f(5) + 1

在程序的世界里,用什么东东来存一个可以记录之前结果值的数据结构呢?

显而易见:数组呗。直接利用下标来存,巴适, 这就是动态规划里的动态,规划就是限定一些边界和初始化。

看到这里,老铁,你就会动态规划了,来看第二题。

No.2

\### leecode 322: 你有三种硬币,2元、5元、7元,每种硬币足够多,买一本书需要27元,用最少的硬币组合

img

怎么感觉像是回到了小学应用题?

--简单分析一下: 最小硬币组合 -> 尽量用大的硬币

这傻不拉几的题谁出的,这么简单

7+7+7=21,21+2+2+2=27, 6枚硬币

卧槽

7+5+5+5+5=27, 5枚硬币

我们可以很暴力的想一想,从大往小的算,可以加起来不超过27,比如

7+7+7+7 > 27 (排除)

7+7+7+5 或者 7 +7 +7+2+2+2 6枚

....

穷举太慢了,还会涉及到很多的重复计算,如果我想要27以内的任何值最小的硬币组合呢,想想都头大了吧。

既然计算机可以通过内存保存之前的内容,又快,很明显,我们开一个数组来保存之前的状态。

重点预警

1.1. 动态规划组成部分1:确定状态

简单的说,解动态规划的时候需要开一个数组,数组的每个元素f[i]或者fi代表什么,类似数学题中x, y, z代表什么

解动态规划需要两个意识:

- 最后一步

- 子问题

最后一步

刚刚第一题不是说了嘛,最后一步的计算结果是5。对于这道题,虽然我们不知道最优策略是什么,但是最优策略肯定是K枚硬币,a1, a2, ....ak面值加起来是27

所以一定有一枚最后的硬币:ak.

除掉这么硬币,前面硬币的面值加起来是27-ak

关键点1:

- 我们不关心前面的k-1枚硬币是怎么拼出27-ak的(可能有一种拼法,也可能有100种拼法),而且我们现在甚至还不知道ak和K, 但是我们确定前面的硬币拼出了27-ak

关键点2:

- 因为是最优策略, 所以拼出27-ak的硬币数一定要最少,否则这就不是最优策略了

img

子问题

- 所以我们就要求:最少用多少枚硬币可以拼出27-ak

- 原问题是最少用多少枚硬币拼出27

- 我们将原问题转化了一个子问题,而且规模更小:27-ak

- 为了简化定义, 我们设状态f(x)=最少用多少枚硬币拼出x

等等,我们还不知道最后的那枚硬币ak是多少

\1. 很明显,最后的那枚硬币只能是2,5或者7

\2. 如果ak是2, f(27)应该是f(27-2)+1(1代表最后一枚硬币2)

\3. 如果ak是5, f(27)应该是f(27-5)+1(1代表最后一枚硬币5)

\4. 如果ak是7, f(27)应该是f(27-7)+1(1代表最后一枚硬币7)

所以使用最少的硬币数=f(27) = min{f(27-2)+1, f(27-5)+1, f(27-7)+1}

1.2. 动态规划组成部分2:转移方程

设状态f(x)=最少用多少枚硬币拼出x

对于任意的x : f(X) = min{f(X-2)+1, f(X-5)+1, f(X-7)+1}

1.3. 动态规划组成部分2:初始条件和边界情况

提出问题

\1. x-2, x-5, x-7 小于0怎么办?

\2. 什么时候停下来?

1.3.1

如果不能拼出Y, 就定义f[Y] = 正无穷

例如f[-1], f[-2] = 正无穷

例如:拼不出f[1]=min{f(-1)+1, f(-3)+1, f(-6)+1}

初始条件:f[0] = 0

2.4. 动态规划组成部分2:计算顺序

计算:f[1], f[2], ... f[27]

当我们计算到f[x], f[x-2], f[x-5], f[x-7] 都已经得到结果了

如图:

img

上图7只需要一个硬币。

f[x] = 最少用多少枚硬币拼出x

f[x] = ∞ 表示无法用硬币拼出x

参考代码

public  static  int coinChange(int [] A, int M ) {

 int[] f = new int[M+1];

 int n = A.length;

 f[0] = 0;

 int i,j;

 for (i = 1; i<=M; i++) {

​    f[i] = Integer.MAX_VALUE;

​    for (j = 0; j< n;j++) {

​        // 边界条件判断

​        if (i >= A[j] && f[i - A[j]] != Integer.MAX_VALUE) {

​            f[i] = Math.min(f[i - A[j]] + 1, f[i]);

​          //  System.out.println(i + "=" +f[i]);

​        }

​    }

 }

 if (f[M] == Integer.MAX_VALUE) {

​    f[M] = -1 ;

 }

 return  f[M];

}

@Test

public void isCoinChange() {

​    int xx = {1,2,3};

​    int b = 6;

​    int i = coinChange(xx, b);

​    Assert.assertNotNull(i);

}

😄

核心代码就4行,是不是很简单~

No.3

\### leecode 62 :不同路径

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

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

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

img

看了上面的解题步骤,按部就班的来

2.1. 动态规划组成部分1:确定状态

最后一步

无论机器人用何种方式到达右下角,总有最后挪动的一步:-向右或者向下

如果所示,我们设右下角的坐标为(m-1,n-1)

那么最后一步的前一步机器人的位置在(m-2,n-1)或者(m-1,n-2)

子问题

那么,如果机器人有x种方式从左上角走到(m-2,n-1), 有Y种方式从左上角走到(m-1,n-2), 则机器人有X+Y的方式走到(m-1,n-1)

问题转化为,机器人有多少种 方式从左上角走到(m-2,n-1)或者(m-1,m-2)

如果走到是(m-2,n-1)如图:

img

我们可以直接干掉最后一列

同理如果是走到(m-1,n-2)行就减少一行。

状态

设fi为机器人有多少种方式从左上角走到(i,j)

2.2. 动态规划组成部分2:转移方程

对于任意一个格子:

fi = fi-1 + fi

1 2 3

1代表机器人有多少种方式走到i

2代表机器人有多少种方式走到fi-1

3代表机器人有多少种方式走到fi

2.3. 动态规划组成部分3:初始条件和边界情况

初始条件:f0=1,因为机器人只有一个方式到左上角

边界情况:i=0或j=0,则前一步只能有一个方向过来,也就是说第0行或者第0列,每走一步只有一种情况,则fi = 1,其他区域都满足转移方程。

3.4. 动态规划组成部分4:计算顺序

按行计算,为什么按行计算呢?

对于这道题来说,按行计算在计算到f1时,f0和f1都已经计算了,同样按列计算这两坐标也计算了,不用再次计算。

- f0 = 1

- 计算第0行:f0,f0,...,f0

- 计算第1行:f1,f1,...,f1

- ...

- 计算第m-1行:fm-1,fm-1,...,fm-1

时间复杂度:O(mn)

img

参考代码


public int uniquePaths(int m, int n) {

​    int[][] f = new int[m][n];

​    int i,j;

​    for (i = 0; i<m; i++) {

​        for (j = 0; j< n; j++) {

​            if (i == 0 || j == 0) {

​                f[i][j] = 1;

​            } else {

​                f[i][j] = f[i -1][j] + f[i][j-1];

​            }

​        }

​    }

​    return f[m-1][n-1];

}



@Test

public void isUniquePaths() {

​    int i = uniquePaths(3, 3);

​    Assert.assertNotNull(i);

}

能看到这里的朋友,你已经超过80%的人,可能现在你的脑袋开始有点晕了,刷题就是这样,刷几道就会头疼,休息下就好了,这玩儿意儿看得就是坚持.

总结一下

什么题可以选择动态规划来做?

1.计数

- 有多少种方式走到右下角

- 有多少种方法选出k个数是的和是sum

2.求最大值最小值

- 从左上角走到右下角路径的最大数字和

- 最长上升子序列长度

3.求存在性

- 取石子游戏,先手是否必胜

- 能不能选出k个数使得和是sum

好叻!接下来咱们整第四道题。

No.4

\### leecode 5. 最长回文子串

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:输入: "babad"

输出: "bab" 注意: "aba" 也是一个有效答案。

示例 2:输入: "cbbd"

输出: "bb"

看了之前的文章,我们就四步走吧

1.1. 动态规划组成部分1:确定状态

简单的说,解动态规划的时候需要开一个数组,数组的每个元素f[i]或者fi代表什么,类似数学题中x, y, z代表什么

在这道题中,我们定义fi 表示字符串 s 的第 i 到 j 个字母组成的串是否为回文串

解动态规划需要两个意识:

- 最后一步

- 子问题

最后一步

我们用示例一来讲解,下图是第一步和第二步的判断过程,很明显最后一步为下标为4的字母b与前面所有元素进行比较,得出最长的回文子串。

img

子问题

img

我们可以看到如果f[i] =f[j],要判定它是一个回文串,需要判定

f[i]j] = f[i+1]f[j-1] : 从i到j是一个回文串,那么从i+1到j-1一定也是一个回文串

也就是如上图需要判定a=a

1.2. 动态规划组成部分2:转移方程

对于从i到j长度的字符串,判定它是一个回文串:

f[i]j] = f[i+1]f[j-1]

同时我们也知道,fi+1这是一个已知的,因为最后一步的上一步已经将结果保存,也就是fi+1 = f[i+2]f[j-2]

1.3. 动态规划组成部分3:初始条件和边界情况

当剩余判定字母个数<3 并且 f[i] = f[j],它一定是回文串。

对于字母本身来说fi,从i到i的字符串,它也是回文。

1.4. 动态规划组成部分4:计算顺序

如上图,我们用j去匹配0~i (i < j)

它的时间复杂度是On^2,由于是二维数据空间复杂度也是On^2

当然也有其他的解决办法如中心扩散和马拉车。

参考代码


// 动态规划

public String longestPalindrome(String s) {

​    // 特判

​    int len = s.length();

​    if (len < 2) {

​        return s;

​    }



​    int maxLen = 1;

​    int begin = 0;



​    // dp[i][j] 表示 s[i, j] 是否是回文串

​    boolean[][] dp = new boolean[len][len];

​    char[] charArray = s.toCharArray();



​    for (int i = 0; i < len; i++) {

​        dp[i][i] = true; // 对本身来说就是回文

​    }

​    for (int j = 1; j < len; j++) {

​        for (int i = 0; i < j; i++) {

​            if (charArray[i] != charArray[j]) {

​                dp[i][j] = false;

​            } else {

​                if (j - i < 3) {

​                    dp[i][j] = true;

​                } else {

​                    dp[i][j] = dp[i + 1][j - 1]; // 要满足这个条件,必需先满足j - i > 3考虑边界

​                }

​            }



​            // 只要 dp[i][j] == true 成立,就表示子串 s[i..j] 是回文,此时记录回文长度和起始位置

​            if (dp[i][j] && j - i + 1 > maxLen) {

​                maxLen = j - i + 1;

​                begin = i;

​            }

​        }

​    }

​    return s.substring(begin, begin + maxLen);

}



@Test

public void islongestPalindrome() {

​    String i = longestPalindrome("babaxaxab");

​    Assert.assertNotNull(i);

}

准备来一道非常实用的题目👍 👍 👍

No.5

\### leecode 10. 正则表达式匹配

给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符

'*' 匹配零个或多个前面的那一个元素

所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。

示例 1:

输入:s = "aab" p = "c a b " (*号无空格)

输出:true

解释:因为 '*' 表示零个或多个,这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 2:

输入:s = "mississippi" p = "misisp*."

输出:false

解释:第二个*不能匹配si

2.1. 动态规划组成部分1:确定状态

wc,你倒是说说怎么确定要用动态规划来做啊?

- 看题目,需要逐步匹配

- 没有时间复杂度空间复杂度限制,你可以选择>On的

- 跟前面题很类似,这里需要考虑* 和 .的情况。

- 尝试根据步骤写出转移方程

在这道题中,我们定义fi 表示字符串 s 的前 i 个字符与 字符串p的前 j 个字符是否匹配

解动态规划需要两个意识:

- 最后一步

- 子问题

最后一步

我们用示例来讲解 :s = "aaab" p = "aa*b"

根据题目意思,我们知道s要被全匹配,我们直接用s去匹配p字符串的每一个字符,这样我们的最后一步就是用s字符串中的b字符去匹配p字符串的每一个字符,匹配最后一个字符为b是否相等。

子问题

有几种情况需要讨论,也就是用s去匹配p最后一个匹配的字符j

- 如果都是字符,只需要判断:fi = fi-1

- 如果是“.” ,说明可以匹配s的最后任意一个字符,也只需:

fi = fi-1

- 如果是“*”,分两种情况一种是匹配零个字符,一种是匹配1个或多个字符

如果是匹配零个字符:fi = fi ,因为如果j是*,我们就可以对p的j-1匹配任意次数,当然零次就是j-2了。

​ 如果是匹配1个或多个字符:fi = fi-1,匹配 s 末尾的一个字符,将该字符扔掉,而该组合还可以继续进行匹配,简单点说,零个我们判定了,如果是一个我们扔掉一个字符,如果能匹配则保存,如果匹配两个,我们是知道匹配s的上一个字符的结果的,直接匹配就行,同样匹配多个也是如此。(匹配多个是根据前一个的匹配结果得出来的)

2.2. 动态规划组成部分2:转移方程

在子问题中我们分析的几种情况就是转移方程

2.3. 动态规划组成部分3:初始条件和边界情况

因为要涉及到i-1和j-1,注意边界

boolean[][] f = new booleanm + 1;

f0=true

2.4. 动态规划组成部分4:计算顺序

用s去匹配p字符串的每一个字符

它的时间复杂度是Onm,由于是二维数据空间复杂度是Onm

参考代码


public boolean isMatch(String s, String p) {

​    int m = s.length();

​    int n = p.length();



​    boolean[][] f = new boolean[m + 1][n + 1];

​    f[0][0] = true;

​    for (int i = 0; i <= m; ++i) {

​        for (int j = 1; j <= n; ++j) {

​            if (p.charAt(j - 1) == '*') {

​                f[i][j] = f[i][j - 2];

​                if (matches(s, p, i, j - 1)) {

​                    f[i][j] = f[i][j] || f[i - 1][j];

​                }

​            } else {

​                if (matches(s, p, i, j)) {

​                    f[i][j] = f[i - 1][j - 1];

​                }

​            }

​        }

​    }

​    return f[m][n];

}



public boolean matches(String s, String p, int i, int j) {

​    if (i == 0) {

​        return false;

​    }

​    if (p.charAt(j - 1) == '.') {

​        return true;

​    }

​    return s.charAt(i - 1) == p.charAt(j - 1);

}

@Test

public void isisMatch() {

​     boolean i = isMatch("aa", "a*");

​     Assert.assertNotNull(i);

}

No.6

继续干,继续干❤️❤️❤️❤️

\### leecode 32. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。

示例 1:

输入:s = "(()"

输出:2

解释:最长有效括号子串是 "()"

示例 2:

输入:s = ")()())"

输出:4

解释:最长有效括号子串是 "()()"

示例 3:

输入:s = ""

输出:0

提示:

0 <= s.length <= 3 * 104

s[i] 为 '(' 或 ')'

看了之前的文章,我们就四步走吧

1.1. 动态规划组成部分1:确定状态

简单的说,解动态规划的时候需要开一个数组,数组的每个元素f[i]或者fi代表什么,类似数学题中x, y, z代表什么

wc,你倒是说说怎么确定要用动态规划来做啊?

- 看题目,需要逐步验证最长长度

- 没有时间复杂度空间复杂度限制,你可以选择>=On的

- 跟前面题很类似,这里需要考虑生成括号的情况。

- 尝试根据步骤写出转移方程

在这道题中,我们定义d[i]表示以下标 ii字符结尾的最长有效括号的长度

解动态规划需要两个意识:

- 最后一步

- 子问题

最后一步

我们用下图来讲解,i作为最后一个括号判断,我们只对为左括号做判断,左括号分两种情况,具体看子问题拆分。

lecoode 32.jpg

子问题

第一种情况为: ...()

因为括号前面可能还有有效的括号,之前我们定义了d[i] 表示下标i字符结尾的最长有效括号的长度,所以可以推导出:

d[i] = d[i-2] + 2

第二种情况为: ...))

321.jpg

如图,下标为2:i - d[i-1] -1

提出一个疑问:在下标2和5之前可能存在多个有效括号,其实都是d[i-1],因为我们定义的:d[i-1] 表示下标i-1字符结尾的最长有效括号的长度

322.jpg

最长有效括号的长度 :

d[i] = x + y

这里x = d[i - d[i-1] -2]

这里y = d[i-1] + 2

因此 :d[i] = d[i - d[i-1] -2] + d[i-1] + 2

1.2. 动态规划组成部分2:转移方程

d[i] 表示下标i字符结尾的最长有效括号的长度

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

1.3. 动态规划组成部分3:初始条件和边界情况

跟之前有些题一样,我们需要判断第i字符去判断第i-1个字符,所以i从1开始遍历,判断数组i-2需要考虑越界。

① ...() : i >=2

② ...)) : i - d[i-1] > 0 对应 :())

1.4. 动态规划组成部分4:计算顺序

从左往右

它的时间复杂度是On,空间复杂度也是On

当然也有其他的解决办法如栈

参考代码


public int longestValidParentheses(String s) {

​    int maxans = 0;

​    int[] dp = new int[s.length()];

​    for (int i = 1; i < s.length(); i++) {

​        if (s.charAt(i) == ')') {

​            if (s.charAt(i - 1) == '(') {

​                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;

​            } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {

​                dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;

​            }

​            maxans = Math.max(maxans, dp[i]);

​        }

​    }

​    return maxans;

}



@Test

public void isLongestValidParentheses() {

​    String s = "()(())";

​    longestValidParentheses(s);

}

No.7

这道题相对于就简单一些啦---来自秃顶的工程师👥👥👥👥👥

\### leecode 42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

421.jpg

输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]

输出:6

解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。

示例 2:

输入:height = [4,2,0,3,2,5]

输出:9

提示:

n == height.length

0 <= n <= 3 * 104

0 <= height[i] <= 105

看了之前的文章,我们就四步走吧

这道题相对而言,提升了难度,常规的题,我们的计算顺序一般是从左到右,或者从右到左,亦或是从上到下。

1.1. 动态规划组成部分1:确定状态

简单的说,解动态规划的时候需要开一个数组,数组的每个元素f[i]或者fi代表什么,类似数学题中x, y, z代表什么

wc,你倒是说说怎么确定要用动态规划来做啊?

- 看题目,需要逐步验证最长长度

- 没有时间复杂度空间复杂度限制,你可以选择>=On的

- 跟前面题很类似,这里需要考虑每一步最高的高度取低位高度,因为可能形成低洼

- 尝试根据步骤写出转移方程

在这道题中,我们定义d[i]表示以下标 i字符结尾的最多的有效雨水

解动态规划需要两个意识:

- 最后一步

- 子问题

最后一步

我们可以利用填满法来降低复杂度。去掉低洼的情况。

先从左到右来看,求出每个位置的最大高度(深度)

image.png

从右往左看,求出每个位置的最大高度

423.jpg

我们在来看它们重叠之后的效果

424.jpg

这样每个位置的最小值 - 高度就是每个位置的蓄水值。

子问题

我们存储了从左到右和从右到左每个位置的最大值

从重叠的图中可以看到最后一个位置的最小值为2,减去高度,蓄水值为0.

1.2. 动态规划组成部分2:转移方程

ans += Math.min(left_max[i], right_max[i]) - height[i];

1.3. 动态规划组成部分3:初始条件和边界情况

1.4. 动态规划组成部分4:计算顺序

从左到右 + 从右到左

它的时间复杂度是On,空间复杂度也是On

当然也有其他的解决办法如栈

参考代码


public int trap(int[] height) {

​    if (height == null || height.length == 0)

​        return 0;

​    int ans = 0;

​    int size = height.length;

​    int[] left_max = new int[size];

​    int[] right_max = new int[size];

​    left_max[0] = height[0];

​    for (int i = 1; i < size; i++) {

​        left_max[i] = Math.max(height[i], left_max[i - 1]);

​    }

​    right_max[size - 1] = height[size - 1];

​    for (int i = size - 2; i >= 0; i--) {

​        right_max[i] = Math.max(height[i], right_max[i + 1]);

​    }

​    for (int i = 1; i < size - 1; i++) {

​        ans += Math.min(left_max[i], right_max[i]) - height[i];

​    }

​    return ans;

}



@Test

public void istrap() {

​    int[] candidates = {2, 0, 6, 1};

​    int i = trap(candidates);

​    Assert.assertNotNull(i);

}

No.8

这道题跟第五题很类似,如果看懂了第五题,那么这题肯定是信手拈来❤️❤️❤️❤️

\### leecode 44. 通配符匹配

给定一个字符串 (s) 和一个字符模式 (p) ,实现一个支持 '?' 和 '*' 的通配符匹配。

'?' 可以匹配任何单个字符。

'*' 可以匹配任意字符串(包括空字符串)。

两个字符串完全匹配才算匹配成功。

说明:

s 可能为空,且只包含从 a-z 的小写字母。

p 可能为空,且只包含从 a-z 的小写字母,以及字符 ? 和 *。

示例 1:

输入:

s = "aa"

p = "a"

输出: false

解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:

s = "aa"

p = "*"

输出: true

解释: '*' 可以匹配任意字符串。

示例 3:

输入:

s = "cb"

p = "?a"

输出: false

解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

示例 4:

输入:

s = "adceb"

p = "ab"

输出: true

解释: 第一个 '' 可以匹配空字符串, 第二个 '' 可以匹配字符串 "dce".

示例 5:

输入:

s = "acdcb"

p = "a*c?b"

输出: false

看了之前的文章,我们就四步走吧

1.1. 动态规划组成部分1:确定状态

简单的说,解动态规划的时候需要开一个数组,数组的每个元素f[i]或者fi代表什么,类似数学题中x, y, z代表什么

wc,你倒是说说怎么确定要用动态规划来做啊?

- 看题目,需要逐步验证最长长度

- 没有时间复杂度空间复杂度限制,你可以选择>=On的

- 跟前面题很类似,这里需要考虑* 和 ?的情况。

- 尝试根据步骤写出转移方程

在这道题中,我们定义fi 表示字符串 s 的前 i 个字符与 字符串p的前 j 个字符是否匹配

解动态规划需要两个意识:

- 最后一步

- 子问题

最后一步

我们用示例来讲解 :s = "aaab" p = "aa*b"

根据题目意思,我们知道s和p要全匹配,我们直接用s去匹配p字符串的每一个字符,这样我们的最后一步就是用s字符串中的b字符去匹配p字符串的每一个字符,匹配最后一个字符为b是否相等。

子问题

这是 ' 动态规划Day two - 正则表达式匹配' 的子问题分析

有几种情况需要讨论,也就是用s去匹配p最后一个匹配的字符j

- 如果都是字符,只需要判断:fi = fi-1

- 如果是“.” ,说明可以匹配s的最后任意一个字符,也只需:

fi = fi-1

- 如果是“*”,分两种情况一种是匹配零个字符,一种是匹配1个或多个字符

如果是匹配零个字符:fi = fi ,因为如果j是*,我们就可以对p的j-1匹配任意次数,当然零次就是j-2了。

如果是匹配1个或多个字符:fi = fi-1,匹配 s 末尾的一个字符,将该字符扔掉,而该组合还可以继续进行匹配,简单点说,零个我们判定了,如果是一个我们扔掉一个字符,如果能匹配则保存,如果匹配两个,我们是知道匹配s的上一个字符的结果的,直接匹配就行,同样匹配多个也是如此。(匹配多个是根据前一个的匹配结果得出来的)

这道题基本上是如出一辙

有几种情况需要讨论,也就是用s去匹配p最后一个匹配的字符j

- 如果都是字符,只需要判断:fi = fi-1

- 如果是“?” ,说明可以匹配s的最后任意一个字符,也只需:

fi = fi-1

- 如果是“”,分两种情况,第一种是不需要使用,第二种是需要使用*

实例 :s = "abc" p = "a*"。

在对s串的a遍历p串的*时,刚好满足dpi = dpi 此时i=1,j=2,

dp1 = dp1=true。 ---不需要使用*

在对s串的b遍历p串的时,刚好满足dpi = fi-1,因为是可以匹配任意一个字母的。

dp2 = dp1=true。---需要使用*

在对s串的c遍历p串的时,刚好满足dpi = fi-1,因为是可以匹配任意一个字母的。

dp3 = dp2=true。---不需要使用*

1.2. 动态规划组成部分2:转移方程

转移方程可以详见子问题分析

1.3. 动态规划组成部分3:初始条件和边界情况

因为要涉及到i-1和j-1,注意边界

boolean[][] f = new booleanm + 1;

f0=true

当f0时,需要判断j是否为,因为可以匹配null串

1.4. 动态规划组成部分4:计算顺序

用s串的每一个字符去匹配p串的每一个字符

它的时间复杂度是Onm,空间复杂度也是Onm

参考代码


public boolean isWildcardMatch(String s, String p) {

​    int m = s.length();

​    int n = p.length();

​    boolean[][] dp = new boolean[m + 1][n + 1];

​    dp[0][0] = true;

​    for (int i = 1; i <= n; ++i) {

​        if (p.charAt(i - 1) == '*') {

​            dp[0][i] = true;

​        } else {

​            break;

​        }

​    }

​    for (int i = 1; i <= m; ++i) {

​        for (int j = 1; j <= n; ++j) {

​            if (p.charAt(j - 1) == '*') {

​                dp[i][j] = dp[i][j - 1] || dp[i - 1][j];

​            } else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {

​                dp[i][j] = dp[i - 1][j - 1];

​            }

​        }

​    }

​    return dp[m][n];

}



@Test

public void isisWildcardMatch() {

​    boolean i = isWildcardMatch("123", "1*");

​    Assert.assertNotNull(i);

}

No.9

这道题就很简单了,放松一下~👍👍👍👍

\### 63. 不同路径 II

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

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

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

63.jpg

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1:

631.jpg

输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]

输出:2

解释:

3x3 网格的正中间有一个障碍物。

从左上角到右下角一共有 2 条不同的路径:

\1. 向右 -> 向右 -> 向下 -> 向下

\2. 向下 -> 向下 -> 向右 -> 向右

示例 2:

632.jpg

输入:obstacleGrid = [[0,1],[0,0]]

输出:1

提示:

m == obstacleGrid.length

n == obstacleGrid[i].length

1 <= m, n <= 100

obstacleGridi 为 0 或 1

本题与

---

里的不同路径1,大致相同,只是增加了障碍物,我们做一下没有障碍物的判断就行了。

2.1. 动态规划组成部分1:确定状态

最后一步

无论机器人用何种方式到达右下角,总有最后挪动的一步:-向右或者向下

如果所示,我们设右下角的坐标为(m-1,n-1)

那么最后一步的前一步机器人的位置在(m-2,n-1)或者(m-1,n-2)

子问题

那么,如果机器人有x种方式从左上角走到(m-2,n-1), 有Y种方式从左上角走到(m-1,n-2), 则机器人有X+Y的方式走到(m-1,n-1)

问题转化为,机器人有多少种 方式从左上角走到(m-2,n-1)或者(m-1,m-2)

如果走到是(m-2,n-1)如图:

634.jpg

我们可以直接干掉最后一列

同理如果是走到(m-1,n-2)行就减少一行。

状态

设fi为机器人有多少种方式从左上角走到(i,j)

2.2. 动态规划组成部分2:转移方程

对于任意一个格子:

fi = fi-1 + fi

1 2 3

1代表机器人有多少种方式走到i

2代表机器人有多少种方式走到fi-1

3代表机器人有多少种方式走到fi

2.3. 动态规划组成部分3:初始条件和边界情况

初始条件:f0=1,因为机器人只有一个方式到左上角

边界情况:i=0或j=0,则前一步只能有一个方向过来,也就是说第0行或者第0列,每走一步只有一种情况,则fi = 1,其他区域都满足转移方程。

如果遇到障碍物,fi = 0。

3.4. 动态规划组成部分4:计算顺序

按行计算,为什么按行计算呢?

对于这道题来说,按行计算在计算到f1时,f0和f1都已经计算了,同样按列计算这两坐标也计算了,不用再次计算。

- f0 = 1 如果第一个是障碍物f0=0

- 计算第0行:f0,f0,...,f0

- 计算第1行:f1,f1,...,f1

- ...

- 计算第m-1行:fm-1,fm-1,...,fm-1

时间复杂度:O(mn)

635.jpg

参考代码


class Solution {

public int uniquePathsWithObstacles(int[][] obstacleGrid) {

​    if (obstacleGrid == null || obstacleGrid.length == 0) {

​        return 0;

​    }



​    // 定义 dp 数组并初始化第 1 行和第 1 列。

​    int m = obstacleGrid.length, n = obstacleGrid[0].length;

​    int[][] dp = new int[m][n];

​    for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {

​        dp[i][0] = 1;

​    }

​    for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {

​        dp[0][j] = 1;

​    }



​    // 根据状态转移方程 dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 进行递推。

​    for (int i = 1; i < m; i++) {

​        for (int j = 1; j < n; j++) {

​            if (obstacleGrid[i][j] == 0) {

​                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

​            }

​        }

​    }

​    return dp[m - 1][n - 1];

}

简单说一下滚动数组的版本,当我们知道当前位置的最多路径数时,我们去求下一个位置的路径数,只需要知道左边和上边的可以了,空间复杂度为o(m)

参考代码


  public int uniquePathsWithObstacles(int[][] obstacleGrid) {

​    int n = obstacleGrid.length, m = obstacleGrid[0].length;

​    int[] f = new int[m];



​    f[0] = obstacleGrid[0][0] == 0 ? 1 : 0;

​    for (int i = 0; i < n; ++i) {

​        for (int j = 0; j < m; ++j) {

​            if (obstacleGrid[i][j] == 1) {

​                f[j] = 0;



​            } else 

​            if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {

​                f[j] += f[j - 1];

​            }

​        }

​    }



​    return f[m - 1];



}

No.10

看到这次分享的最后一题啦,能看到这里的人呀,都是人才。❤️❤️❤️❤️

来一道比较简单的题目吧!!!

\### leecode 64. 最小路径和

给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明:每次只能向下或者向右移动一步。

示例 1:

输入:grid = [[1,3,1],[1,5,1],[4,2,1]]

输出:7

解释:因为路径 1→3→1→1→1 的总和最小。

示例 2:

输入:grid = [[1,2,3],[4,5,6]]

输出:12

提示:

m == grid.length

n == grid[i].length

1 <= m, n <= 200

0 <= gridi <= 100

看了之前的题解,想想就明白了,这里用动态规划解题,考虑一下几点:

\1. 边界处理

\2. 中间的路径

\3. 这里的结果会有M*N次所以每个格子的结果都会作比较,我们取较小值就可以了

dpi 表示从左上角出发到 (i,j)(i,j) 位置的最小路径和

初始条件:dp0=grid0

当 i>0 j=0时dpi=dpi-1 + gridi; // gridi为最后一个格子的值

当 i=0 j>0时dp0=dp0 + grid0;

当 i>0 j>0时dpi-1=min(dpi-1,dpi) + gridi;

参考代码:


class Solution {

​    public int minPathSum(int[][] grid) {

​        if (grid == null || grid.length == 0 || grid[0].length == 0) {

​            return 0;

​        }

​        int rows = grid.length, columns = grid[0].length;

​        int[][] dp = new int[rows][columns];

​        dp[0][0] = grid[0][0];

​        for (int i = 1; i < rows; i++) {

​            dp[i][0] = dp[i - 1][0] + grid[i][0];

​        }

​        for (int j = 1; j < columns; j++) {

​            dp[0][j] = dp[0][j - 1] + grid[0][j];

​        }

​        for (int i = 1; i < rows; i++) {

​            for (int j = 1; j < columns; j++) {

​                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];

​            }

​        }

​        return dp[rows - 1][columns - 1];

​    }

}

❤️❤️❤️❤️

非常感谢人才们能看到这里,如果这个文章写得还不错,觉得有点东西的话 求点赞👍 求关注❤️ 求分享👥 对暖男我来说真的 非常有用!!!

如果本篇博客有任何错误,请批评指教,不胜感激 !

\>文末福利,最近整理一份面试资料《Java面试通关手册》,覆盖了Java核心技术、JVM、Java并发、SSM、微服务、数据库、数据结构等等。获取方式:搜汀雨笔记,更多内容陆续奉上。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: