vlambda博客
学习文章列表

前言

希望上海疫情尽早过去，其实有一段稳定的时间是比较适合沉淀一下技术的，多少还是自己有些散漫，近期应该会恢复更新《手撕MySQL》系列文章。这篇文章通过一道经典例题：最长公共子序列，给大家讲讲动态规划，并且给出一道LeetCode周赛动态规划题作为练手并讲解，相信看完文章之后，你会对动态规划有更深的理解。

关于后面的dp练手题，是某次周赛的第四题，借助这题，我会在后面分析部分讲解如何从读题开始，沉浸式一步一步解决一个算法题。这个过程适用于所有的题目，比较重要，当然我们先从经典的最长公共子序列入手。

最长公共子序列

题目链接：LeetCode 1143

题目

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回0。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串，如 ace是 abcde的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

分析

设dp[i] [j]为text1的前i个字符组成的串str1和text2的前j个字符组成的串str2的最长公共子序列，初始化时：dp[0] [j]与dp[i] [0]都为0，因为str1为空或者str2为空都将无法构成子序列

根据上面的表述，text1[i-1]是str1的最后一个字符，而不是text1[i]，因为下标从0开始；同理test2[j-1]表示str2的最后一个字符

那么就可以开始讨论状态转移方程：如果 text[i-1] == text2[j-1]，表示str1的最后一个字符和str2的最后一个字符相等，那么dp[i] [j] = dp[i-1] [j-1] + 1，可以理解成两个字符串都去掉相等的末尾字符，然后在前面剩余的字符中再求最长公共子序列，最后结果+1，因为这个过程是可以追溯的，因此满足动态规划的要求

如果 text[i-1] != text2[j-1]，则dp[i] [j] = max(dp[i-1] [j], dp[i] [j-1]) ，因为dp[i-1] [j]和dp[i] [j-1]都是已经求出来的字问题的解，所以可以追溯，既然str1和str2的末尾不一样，那么就让str1去掉末尾和str2求解或者str2去掉末尾和str1求解，两者取最大值即可

代码

用的是go语言，但语言不是障碍～

用地毯覆盖后的最少白色砖块

题目链接：LeetCode 2209

题目

给你一个下标从 0 开始的 二进制 字符串 floor ，它表示地板上砖块的颜色。

• floor[i] = '0' 表示地板上第 i 块砖块的颜色是 黑色 。

• floor[i] = '1' 表示地板上第 i 块砖块的颜色是 白色 。

同时给你 numCarpets 和 carpetLen 。你有 numCarpets 条 黑色 的地毯，每一条 黑色 的地毯长度都为 carpetLen 块砖块。请你使用这些地毯去覆盖砖块，使得未被覆盖的剩余 白色 砖块的数目 最小 。地毯相互之间可以覆盖。

请你返回没被覆盖的白色砖块的 最少 数目。

分析

其实在拿到题的一开始，如果看不太明白题意，建议先对照输入输出样例去梳理，比如对于如下输入输出

结合样例你大概懂了题意，好像是要用黑色的地毯尽可能去覆盖白色的连续区域，使得最后剩余的白色最少。大概明白做什么之后，去看输入输出数据的取值范围，因为这涉及到你设计的算法的时间复杂度（主要是时间），如下：

错误思路

floor长度1000，看样子可以写一个O(N^2)的算法，你放心了。然后想：既然是尽可能去覆盖白色连续区域，且每次就是拿一个长度为L的地毯去覆盖，那么我只要每次找一个长度为L的拥有最多白色的块的区间去给他覆盖不就行了，然后把白色改成黑色，外循环是地毯数量，核心是贪心！我又行了！

下面给出一组测试数据：

如果是贪心，那么首先会找到连续的3个1的部分，然后将其修改为100001，然后再找到包含一个1的长度为3的区间，将其修改为000001或者100000，无法到达最优效果：第一次覆盖前3块，第二次覆盖后3块。

正确思路

对于给出的数据，思考是否能使用dp求解，对于动态规划来说，首先要确定规模，一维的dp本题无法胜任，因为地毯数量有多块。

如果是二维dp，那么i和j分别表示什么，一般来说：我习惯于将j设置为被具体操作的“对象”空间（就像是0-1背包我会将背包空间设置为j，而物品的种类设置为i，因为所有i种物品都会放置在j大小的空间中，背包空间此时是被操作"对象"），本题所有的地毯覆盖到一个floor上，因此j的纬度是地砖数量（那么i的维度就是地毯的数量）

最终dp[i] [j]表示使用i块地毯覆盖前j块砖，所剩余的白色的地砖的最少数量

下面给出状态转移方程：

如果第i块地毯选择覆盖下标为j的地砖，则dp[i] [j] = dp[i-1] [j-carpetLen] ，表示只考虑前i-1块地毯去覆盖前j-carpetLen位置的最少白色块数量（因为覆盖了第i块的位置全都变黑）

如果第i块地毯选择不覆盖下标为j的地砖，则dp[i] [j] = dp[i] [j-1]+(floor[j] - '0') ，相当于只考虑用i块地毯去覆盖j-1的地砖，且可能第j块砖是白色的，因此要加上

代码

结束

建议在看过文章之后自己去做一下1143和2209两道题，相信你对动态规划的掌握一定会更上一层。算法水平在面试笔试当中还是十分重要的，经典动态规划题更是很多题目的模板出处，值得学习。