动态规划框架
# 初始化 base case dp[0][0][...] = base # 进行状态转移 for 状态1 in 状态1的所有取值: for 状态2 in 状态2的所有取值: for ... dp[状态1][状态2][...] = 求最值(选择1,选择2...)509. 斐波那契数
斐波那契数,通常用 F(n) 表示,形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:
F(0) = 0,F(1) = 1
F(n) = F(n - 1) + F(n - 2),其中 n > 1
给你 n ,请计算 F(n) 。
class Solution { public: int fib(int n) { if(n==0) return 0;//不考虑边界可能发生段错误 vector322. 零钱兑换dp(n+1); dp[1]=1; for(int i=2;i<=n;i++){ dp[i] = dp[i-1]+dp[i-2]; } return dp[n]; } };
给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1:
输入:coins = [1, 2, 5], amount = 11
输出:3
解释:11 = 5 + 5 + 1
示例 2:
输入:coins = [2], amount = 3
输出:-1
示例 3:
输入:coins = [1], amount = 0
输出:0
示例 4:
输入:coins = [1], amount = 1
输出:1
示例 5:
输入:coins = [1], amount = 2
输出:2
提示:
1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104
class Solution { public: int coinChange(vector300. 最长递增子序列& coins, int amount) { int Max = amount + 1; vector dp(amount + 1, Max); dp[0] = 0;// base case for (int i = 1; i <= amount; i++) { // 从1数到amount,自底向上 for (int j = 0; j < (int)coins.size(); j++) { // 遍历硬币 if (coins[j] <= i) { // 更新子问题最优解 dp[i] = min(dp[i], dp[i - coins[j]] + 1); } } } return dp[amount] > amount ? -1 : dp[amount]; } };
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1:
输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。
示例 2:
输入:nums = [0,1,0,3,2,3]
输出:4
示例 3:
输入:nums = [7,7,7,7,7,7,7]
输出:1
提示:
1 <= nums.length <= 2500
-104 <= nums[i] <= 104
注意「子序列」和「子串」这两个名词的区别,子串一定是连续的,而子序列不一定是连续的。
动态规划解法:
定义dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。
class Solution { public: int lengthOfLIS(vector& nums) { int res(1); vector dp(nums.size(),1); for(int i = 0; i < nums.size(); i++){ for(int j = 0; j < i; j++){ if(nums[i] > nums[j]){ dp[i] = max(dp[i], dp[j]+1);//在nums[j]的基础上计算nums[i]的dp[i]值 res = max(res, dp[i]); } } } return res; } };
二分查找解法
其实最长递增子序列和一种叫做 patience game 的纸牌游戏有关,甚至有一种排序方法就叫做 patience sorting(耐心排序)。
类似蜘蛛纸牌的玩法。
这个解法先放一放,今天的重点是动态规划,不能跑偏。
给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组 是数组中的一个连续部分。
示例 1:
输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
示例 2:
输入:nums = [1]
输出:1
示例 3:
输入:nums = [5,4,-1,7,8]
输出:23
提示:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
此题不能用滑动窗口,因为数组中的数字可以是负数,不知道何时缩小左边界。
不能用动态规划时这样定义dp[i]:nums[0…i] 中的「最大的子数组和」为 dp[i]。(可以是断的)
因为子数组一定是连续的,按照我们当前 dp 数组定义,并不能保证 nums[0…i] 中的最大子数组与 nums[i+1] 是相邻的,也就没办法从 dp[i] 推导出 dp[i+1]。所以说我们这样定义 dp 数组是不正确的,无法得到合适的状态转移方程。
定义dp[i]:以 nums[i] 为结尾的「最大子数组和」为 dp[i]。(一定是连续的)
class Solution { public: int maxSubArray(vector72. 编辑距离& nums) { if(nums.size()==0) return 0; vector dp(nums.size(),0); int maxLength = nums[0]; dp[0] = nums[0]; for(int i = 1; i < nums.size(); i++){ dp[i] = max(nums[i], dp[i-1] + nums[i]); //以 nums[i] 为结尾的最大子数组和要么是自己,要么是自己加上以 nums[i-1] 为结尾的最大子数组和 maxLength = max(maxLength, dp[i]); } return maxLength; } };
给你两个单词 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 <= 500
word1 和 word2 由小写英文字母组成
dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数
所以,
当 word1[i] == word2[j],dp[i][j] = dp[i-1][j-1];
当 word1[i] != word2[j],dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
其中,dp[i-1][j-1] 表示替换 *** 作,dp[i-1][j] 表示删除 *** 作,dp[i][j-1] 表示插入 *** 作。
增删改 *** 作的顺序可以是任意的,因此我们可以按 字符串顺序的考虑三种可能的 *** 作。
注意,针对第一行,第一列要单独考虑,我们引入 ‘’ 下图所示:
第一行,是 word1 为空变成 word2 最少步数,就是插入 *** 作
第一列,是 word2 为空,需要的最少步数,就是删除 *** 作
由于计算dp[i][j] 需要知道dp[i-1][j-1], dp[i-1][j], dp[i][j-1]的值,所以我们需要先初始化计算边界:
很显然在i0 和 j0时候即其中一个为空串的情况,那么编辑距离就是另一个串的长度(不断执行增加或者删除 *** 作)。
for(int i = 0; i <= n; i++) dp[i][0] = i;
for(int j = 0; j <= m; j++) dp[0][j] = j;
class Solution { public: int minDistance(string word1, string word2) { int dp[501][501]; int n= word1.size(), m = word2.size(); for(int i = 0; i <= n; i++) dp[i][0] = i; for(int j = 0; j <= m; j++) dp[0][j] = j; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){ if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1]; else dp[i][j] = 1 + min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]}); } return dp[n][m]; } };10. 正则表达式匹配
给你一个字符串 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
解释:".” 表示可匹配零个或多个(’*’)任意字符(’.’)。
示例 4:
输入:s = “aab” p = “cab”
输出:true
解释:因为 ‘*’ 表示零个或多个,这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。
示例 5:
输入:s = “mississippi” p = “misisp*.”
输出:false
提示:
1 <= s.length <= 20
1 <= p.length <= 30
s 只含小写英文字母。
p 只含小写英文字母,以及字符 . 和 *。
保证每次出现字符 * 时,前面都匹配到有效的字符
好难啊没太懂
class Solution { public: bool isMatch(string s, string p) { int m = s.size(); int n = p.size(); auto matches = [&](int i, int j) { if (i == 0) { return false; } if (p[j - 1] == '.') { return true; } return s[i - 1] == p[j - 1]; }; vector> f(m + 1, vector (n + 1)); f[0][0] = true; for (int i = 0; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (p[j - 1] == '*') { f[i][j] |= f[i][j - 2]; if (matches(i, j - 1)) { f[i][j] |= f[i - 1][j]; } } else { if (matches(i, j)) { f[i][j] |= f[i - 1][j - 1]; } } } } return f[m][n]; } };
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)