用 javascript 分类刷 leetcode3. 动态规划 (图文视频讲解)
什么是动态规划
动态规划,英文:Dynamic Programming
,简称DP
,将问题分解为互相重叠的子问题,通过反复求解子问题来解决原问题就是动态规划,如果某一问题有很多重叠子问题,使用动态规划来解是比较有效的。
求解动态规划的核心问题是穷举,但是这类问题穷举有点特别,因为这类问题存在「重叠子问题」,如果暴力穷举的话效率会极其低下。动态规划问题一定会具备「最优子结构」,才能通过子问题的最值得到原问题的最值。另外,虽然动态规划的核心思想就是穷举求最值,但是问题可以千变万化,穷举所有可行解其实并不是一件容易的事,只有列出正确的「状态转移方程」才能正确地穷举。重叠子问题、最优子结构、状态转移方程就是动态规划三要素
动态规划和其他算法的区别
动态规划和分治的区别:动态规划和分治都有最优子结构 ,但是分治的子问题不重叠
动态规划和贪心的区别:动态规划中每一个状态一定是由上一个状态推导出来的,这一点就区分于贪心,贪心没有状态推导,而是从局部直接选最优解,所以它永远是局部最优,但是全局的解不一定是最优的。
动态规划和递归的区别:递归和回溯可能存在非常多的重复计算,动态规划可以用递归加记忆化的方式减少不必要的重复计算
动态规划的解题方法
递归+记忆化(自顶向下)
动态规划(自底向上)
解动态规划题目的步骤
根据重叠子问题定义状态
寻找最优子结构推导状态转移方程
确定 dp 初始状态
确定输出值
斐波那契的动态规划的解题思路
暴力递归
递归 + 记忆化
动态规划
滚动数组优化
动态规划 + 降维,(降维能减少空间复杂度,但不利于程序的扩展)
70. 爬楼梯 (medium)
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
示例 1:
输入:n = 2 输出:2 解释:有两种方法可以爬到楼顶。
1 阶 + 1 阶
2 阶
示例 2:
输入:n = 3 输出:3 解释:有三种方法可以爬到楼顶。
1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶
提示:
1 <= n <= 45
方法 1.动态规划
思路:因为每次可以爬 1 或 2 个台阶,所以到第 n 阶台阶可以从第 n-2 或 n-1 上来,其实就是斐波那契的 dp 方程
复杂度分析:时间复杂度
O(n)
,空间复杂度O(1)
Js:
198. 打家劫舍 (medium)
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。
示例 1:
输入:[1,2,3,1]输出:4 解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。示例 2:
输入:[2,7,9,3,1]输出:12 解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示:
1 <= nums.length <= 1000 <= nums[i] <= 400
思路:
dp[i]
表示 0-i 能偷的最大金额,dp[i]
由两种情况中的最大值转移过来dp[i - 2] + nums[i]
表示偷当前位置,那么 i-1 的位置不能偷,而且需要加上dp[i-2]
,也就是前 i-2 个房间的金钱dp[i - 1]
表示偷当前位置,只偷 i-1 的房间复杂度:时间复杂度
O(n)
,遍历一次数组,空间复杂度O(1)
,状态压缩之后是O(1)
,没有状态压缩是O(n)
js:
343. 整数拆分 (medium)
给定一个正整数 n ,将其拆分为 k 个 正整数 的和( k >= 2 ),并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例 1:
输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。示例 2:
输入: n = 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
提示:
2 <= n <= 58
思路:
dp[i]
为正整数 i 拆分之后的最大乘积,循环数字 n,对每个数字进行拆分,取最大的乘积,状态转移方程:dp[i] = Math.max(dp[i], dp[i - j] * j, (i - j) * j)
,j*(i-j)
表示把 i 拆分为j
和 i-j 两个数相乘,j * dp[i-j]
表示把i
拆分成j
和继续把(i-j)
这个数拆分,取(i-j)
拆分结果中的最大乘积与 j 相乘复杂度:时间复杂度
O(n^2)
,两层循环。空间复杂度O(n)
,dp
数组的空间
js:
509. 斐波那契数(easy)
斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:
F(0) = 0,F(1) = 1F(n) = F(n - 1) + F(n - 2),其中 n > 1 给定 n ,请计算 F(n) 。
示例 1:
输入:n = 2 输出:1 解释:F(2) = F(1) + F(0) = 1 + 0 = 1 示例 2:
输入:n = 3 输出:2 解释:F(3) = F(2) + F(1) = 1 + 1 = 2 示例 3:
输入:n = 4 输出:3 解释:F(4) = F(3) + F(2) = 2 + 1 = 3
提示:
0 <= n <= 30
方法 1.动态规划
思路:自底而上的动态规划
复杂度分析:时间复杂度
O(n)
,空间复杂度O(1)
Js:
10. 正则表达式匹配(hard)
给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符'*' 匹配零个或多个前面的那一个元素所谓匹配,是要涵盖 整个 字符串 s 的,而不是部分字符串。
示例 1:
输入:s = "aa", p = "a"输出:false 解释:"a" 无法匹配 "aa" 整个字符串。示例 2:
输入:s = "aa", p = "a*"输出:true 解释:因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此,字符串 "aa" 可被视为 'a' 重复了一次。示例 3:
输入:s = "ab", p = "."输出:true 解释:"." 表示可匹配零个或多个('*')任意字符('.')。
提示:
1 <= s.length <= 201 <= p.length <= 30s 只包含从 a-z 的小写字母。p 只包含从 a-z 的小写字母,以及字符 . 和 *。保证每次出现字符 * 时,前面都匹配到有效的字符
方法 1.动态规划
思路:
dp[i][j]
表示 s 的前 i 个字符能否和 p 的前 j 个字符匹配,分为四种情况,看图复杂度:时间复杂度
O(mn)
,m,n 分别是字符串 s 和 p 的长度,需要嵌套循环 s 和 p。空间复杂度O(mn)
,dp 数组所占的空间
js:
64. 最小路径和 (medium)
给定一个包含非负整数的 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.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 100
思路:
dp[i][j]
表示从矩阵左上角到(i,j)
这个网格对应的最小路径和,只要从上到下,从左到右遍历网格,当前最小路径和就是当前的数值加上上面和左边左小的。复杂度:时间复杂度
O(mn)
,m、n 分别是矩阵的长和宽。空间复杂度如果原地修改是O(1)
,如果新建 dp 数组就是O(mn)
js:
72. 编辑距离 (hard)
给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
插入一个字符删除一个字符替换一个字符
示例 1:
输入:word1 = "horse", word2 = "ros"输出:3 解释:horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e')示例 2:
输入:word1 = "intention", word2 = "execution"输出:5 解释:intention -> inention (删除 't')inention -> enention (将 'i' 替换为 'e')enention -> exention (将 'n' 替换为 'x')exention -> exection (将 'n' 替换为 'c')exection -> execution (插入 'u')
提示:
0 <= word1.length, word2.length <= 500word1 和 word2 由小写英文字母组成
方法 1.动态规划
思路:
dp[i][j]
表示 word1 前 i 个字符和 word2 前 j 个字符的最少编辑距离。如果
word1[i-1] === word2[j-1]
,说明最后一个字符不用操作,此时dp[i][j] = dp[i-1][j-1]
,即此时的最小操作数和 word1 和 word2 都减少一个字符的最小编辑数相同如果
word1[i-1] !== word2[j-1]
,则分为三种情况word1 删除最后一个字符,状态转移成
dp[i-1][j]
,即dp[i][j] = dp[i-1][j] + 1
,+1 指删除操作word1 在最后加上一个字符,状态转移成
dp[i][j-1]
,即dp[i][j] = dp[i][j-1] + 1
,+1 指增加操作word1 替换最后一个字符,状态转移成
dp[i-1][j-1]
,即 dp[i] [j] = dp[i-1] [j-1] + 1,+1 指替换操作复杂度:时间复杂度是
O(mn)
,m 是 word1 的长度,n 是 word2 的长度。空间复杂度是O(mn)
,需要用 m * n 大小的二维数字存储状态。
Js:
62. 不同路径 (medium)
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
示例 1:
输入:m = 3, n = 7 输出:28 示例 2:
输入:m = 3, n = 2 输出:3 解释:从左上角开始,总共有 3 条路径可以到达右下角。
向右 -> 向下 -> 向下
向下 -> 向下 -> 向右
向下 -> 向右 -> 向下
示例 3:
输入:m = 7, n = 3 输出:28 示例 4:
输入:m = 3, n = 3 输出:6
提示:
1 <= m, n <= 100 题目数据保证答案小于等于 2 * 109
方法 1.动态规划
思路:由于在每个位置只能向下或者向右, 所以每个坐标的路径和等于上一行相同位置和上一列相同位置不同路径的总和,状态转移方程:
f[i][j] = f[i - 1][j] + f[i][j - 1]
;复杂度:时间复杂度
O(mn)
。空间复杂度O(mn)
,优化后O(n)
js:
312. 戳气球 (hard)
有 n 个气球,编号为 0 到 n - 1,每个气球上都标有一个数字,这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球,你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1 或 i + 1 超出了数组的边界,那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。
示例 1:输入:nums = [3,1,5,8]输出:167 解释:nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []coins = 315 + 358 + 138 + 181 = 167 示例 2:
输入:nums = [1,5]输出:10
提示:
n == nums.length1 <= n <= 3000 <= nums[i] <= 100
方法 1:动态规划
思路:
dp[i][j]
表示开区间(i,j)
能拿到的的金币,k 是这个区间 最后一个 被戳爆的气球,枚举i
和j
,遍历所有区间,i-j
能获得的最大数量的金币等于 戳破当前的气球获得的金钱加上之前i-k
、k-j
区间中已经获得的金币复杂度:时间复杂度
O(n^3)
,n 是气球的数量,三层遍历。空间复杂度O(n^2)
,dp 数组的空间。
js:
279. 完全平方数 (medium)
给你一个整数 n ,返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。
示例 1:
输入:n = 12 输出:3 解释:12 = 4 + 4 + 4 示例 2:
输入:n = 13 输出:2 解释:13 = 4 + 9 提示:
1 <= n <= 104
方法 1:动态规划
思路:
dp[i]
表示i
的完全平方和的最少数量,dp[i - j * j] + 1
表示减去一个完全平方数j
的完全平方之后的数量加 1 就等于dp[i]
,只要在dp[i]
,dp[i - j * j] + 1
中寻找一个较少的就是最后dp[i]
的值。复杂度:时间复杂度
O(n* sqrt(n))
,n是输入的整数,需要循环n次,每次计算dp方程的复杂度sqrt(n)
,空间复杂度O(n)
js:
视频讲解:传送门
评论