手机网站建设哪家便宜,学做网站赚钱方法,wordpress 主题 速度快,做建材上哪个网站比较好动态规划(待完善)
动规五部曲分别为#xff1a;
确定dp数组#xff08;dp table#xff09;以及下标的含义确定递推公式#xff08;状态转移公式#xff09;dp数组如何初始化确定遍历顺序举例推导dp数组、
动态规划的核心就是递归剪枝#xff08;存储键值#xff0c;…动态规划(待完善)
动规五部曲分别为
确定dp数组dp table以及下标的含义确定递推公式状态转移公式dp数组如何初始化确定遍历顺序举例推导dp数组、
动态规划的核心就是递归剪枝存储键值下次不再访问用空间换时间
找问题的最好方式就是把dp数组打印出来看看究竟是不是按照自己思路推导的 这道题目我举例推导状态转移公式了么 我打印dp数组的日志了么 打印出来了dp数组和我想的一样么 或者更清晰的知道自己究竟是哪一点不明白是状态转移不明白还是实现代码不知道该怎么写还是不理解遍历dp数组的顺序。
动态规划英文Dynamic Programming简称DP如果某一问题有很多重叠子问题使用动态规划是最有效的。 所以动态规划中每一个状态一定是由上一个状态推导出来的这一点就区分于贪心贪心没有状态推导而是从局部直接选最优的例如有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。
动态规划中dp[j]是由dp[j-weight[i]]推导出来的然后取max(dp[j], dp[j - weight[i]] value[i])。
但如果是贪心呢每次拿物品选一个最大的或者最小的就完事了和上一个状态没有关系。
所以贪心解决不了动态规划的问题。
动态规划的解题步骤1确定dp数组以及下标含义 2确定递推公式 3dp数组如何初始化 4确定遍历顺序 5例举推导dp数组。
【基础题目】
【509】斐波那契数列
解题步骤
1确定dp数组以及下标含义
dp[i]: 第i个数的斐波那契数值是dp[i]。
2确定递推公式
dp[i] dp[i-1]dp[i-2]
3dp数组如何初始化
dp[0] 0 dp[1] 1
4确定遍历顺序
从前向后遍历
5例举推导dp数组。
按照这个递推公式dp[i] dp[i - 1] dp[i - 2]我们来推导一下当N为10的时候dp数组应该是如下的数列
0 1 1 2 3 5 8 13 21 34 55
如果代码写出来发现结果不对就把dp数组打印出来看看和我们推导的数列是不是一致的。
//动态规划基础问题
/*递归的方法 时间复杂度o(n^2) 空间复杂度o(1)*/
class Solution {
public:int fib(int n) {if(n2)return n;return fib(n-1)fib(n-2);}
};
/*动态规划的方法 时间复杂度o(n) 空间复杂度o(n)(经典做法)*/
class Solution {
public:int fib(int n) {if(n2)return n;vectorint dp(n1);dp[0] 0;dp[1] 1;for(int i 2;in1;i){dp[i] dp[i-1]dp[i-2];}return dp[n];}
};/*动态规划简写 时间复杂度o(n) 空间复杂度o(1)*/
class Solution {
public:int fib(int n) {if(n2)return n;vectorint dp(2);dp[0] 0;dp[1] 1;for(int i 2;in1;i){int sum dp[0]dp[1];dp[0] dp[1]; dp[1] sum;}return dp[1];}
};【70】爬楼梯
确定递归数列找规律 f(n) f(n-1)f(n-2) 确定终值f(1) 1 f(0) 0 存储节点定义数组存储节点 最标准的做法要是还要优化空间复杂度就考虑上面的做法
class Solution {
public:int climbStairs(int n) {if(n2)return n;//(f(1) 1,f(2) 2)vectorint f(n1);f[1] 1;f[2] 2;for(int i 3;in1;i){f[i] f[i-1]f[i-2];}return f[n];}
};【118】杨辉三角
注意申请数组具体那一行 注意改变数组的长度的函数resize(为了防止0出现)
class Solution {
public:vectorvectorint generate(int numRows) {vectorvectorint ret(numRows);for (int i 0; i numRows; i) {ret[i].resize(i 1);ret[i][0] ret[i][i] 1;for (int j 1; j i; j) {ret[i][j] ret[i - 1][j] ret[i - 1][j - 1];}}return ret;}
};
【背包问题】
【0-1背包】
对于面试掌握01背包和完全背包多重背包。
基础引用对于01背包就是m个物品给定对应的重量和价值最大容量为n这些物品你只能选一个或者不选01求最大价值。
动态规划五部曲
1确定dp数组以及下标的含义dp[i] [j ]:表示下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。
2确定递推公式
放物品i由dp[i - 1] [j]推出即背包容量为j里面不放物品i的最大价值此时dp[i] [j]就是dp[i - 1] [j]。(其实就是当物品i的重量大于背包j的重量时物品i无法放进背包中所以背包内的价值依然和前面相同。)放物品i由dp[i - 1] [j - weight[i]]推出dp[i - 1] [j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值那么dp[i - 1] [j - weight[i]] value[i] 物品i的价值就是背包放物品i得到的最大价值
所以递归公式 dp[i] [j] max(dp[i - 1] [j], dp[i - 1] [j - weight[i]] value[i]);
3初始化dp数组
后面的公式是根据前面来推导的所以初始化正确了才能导致dp数组正确
状态转移方程 dp[i] [j] max(dp[i - 1] [j], dp[i - 1] [j - weight[i]] value[i]); 可以看出i 是由 i-1 推导出来那么i为0的时候就一定要初始化。
要求出 dp[ 0 ] [ j]:也就是求种类0在不同重量下的最大价值当jweight[0]的时候肯定装不下都为0.所以j从weight[0]开始初始化都为value[0]: (4)确定遍历顺序先遍历物品再遍历重量
for(int i 1;im;i){for(int j 0;jm;j){if(jweight[i]){dp[i][j] dp[i-1][j];//不放}else{dp[i][j] max(dp[i-1][j],dp[i-1][j-weight[i]]value[i]);//放}}
}5举例推导dp数组 #include iostream
#include unordered_map
#include vector
using namespace std;
class Solution{
public:int maxSolution( vectorint weight,vectorint value,int m,int n){//确定dp数组vectorvectorint dp(m,vectorint(n1,0));//要包含一个0//初始化dp数组 dp[i-1][j] 初始化 dp[0][j]for(int j weight[0];jn;j){dp[0][j] value[0];}for(int i 1;im;i){//遍历背包种类 种类1已经初始化过了要从2开始for(int j weight[0];jn;j){//遍历重量if(jweight[i])dp[i][j] dp[i-1][j];else dp[i][j] max( dp[i-1][j-weight[i]]value[i],dp[i-1][j]);}}coutdp[m-1][n]endl;}};int main()
{int m;//背包种类int n;//空间容量 bagweightvectorint weight(m,0);vectorint value(m,0);
// cin mn;
// for(int i 0;im;i){
// cin cap[i];
// }
// for(int i 0;im;i){
// cin value[i];
// }m 3;//背包种类n 4;//最大容量是4weight {1,3,4};//重量value {15,20,20};//价值Solution s;int res s.maxSolution(weight,value,m,n);return 0;
}【416】分割等和子集
0-1背包是可以用回溯的方式去做的和【698】【473】都有相同的做法。
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。
j:容量dp[j]最大价值可以看到都是倒叙取最大值最后的dp数组是
0123456789101101111566661011 class Solution {
public:bool canPartition(vectorint nums) {int sum 0;for(auto num:nums){sumnum;}if(sum%2 1)return false;//要是不能平分直接退出int n sum/2;vectorint dp(n1,0);//初始化dp数组//dp遍历for(int i 0;inums.size();i){for(int jn;jnums[i];j--){//特别注意这个nums[i]dp[j] max(dp[j],dp[j-nums[i]]nums[i]);couti:i dp[j]:dp[j]endl;}}//判断if(dp[n] n)return true;return false;}
};
【1049】最后一块石头的重量
有一堆石头用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合从中选出任意两块石头然后将它们一起粉碎。假设石头的重量分别为 x 和 y且 x y。那么粉碎的可能结果如下
如果 x y那么两块石头都会被完全粉碎如果 x ! y那么重量为 x 的石头将会完全粉碎而重量为 y 的石头新重量为 y-x。
最后最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下就返回 0。
class Solution {
public:int lastStoneWeightII(vectorint stones) {int n stones.size();int sum 0;for(auto item:stones){sumitem;}int target sum/2;vectorint dp(target1,0);for(int i 0;in;i){for(int j target;jstones[i];j--){dp[j] max(dp[j],dp[j-stones[i]]stones[i]);}}return sum-2*dp[target];//注意最后返回的数值}
};【494】目标和
【17】一和零
【32】最长有效括号
给你一个只包含 ‘(’ 和 ‘)’ 的字符串找出最长有效格式正确且连续括号子串的长度。 看到最长就可以开始考虑用动规了 解 (1)确定dp数组和其下标 dp[i] :到[0,i]的最长有效子串长度一维就够了不依赖后面的字符不需要移动 (2)确定状态转移方程
if(s[i] )){if(s[i-1] (){dp[i] dp[i-1]2;} else{dp[i] dp[i-1];}
}else{//没有子串计数dp[i] dp[i-1];
}
【完全背包】
完全背包内层循环从头开始
【322】零钱兑换
class Solution {
public:int coinChange(vectorint coins, int amount) {//初始化dp数组vectorint dp(amount1,INT_MAX);dp[0] 0;for(int i 0;icoins.size();i){for(int j coins[i];jamount;j){//遍历背包 注意初始化的位置if(dp[j-coins[i]] !INT_MAX){// 如果dp[j - coins[i]]是初始值则跳过dp[j] min(dp[j],dp[j-coins[i]]1);}}}if(dp[amount] INT_MAX) return -1;return dp[amount];}
};
遍历的过程
以coins [1,2,5]amount 11为例子
01234567891011初始化0MMMMMMMMMMM1(只有1)0123456789101121或201122334455651或2或5011221223323
【139】单词拆分
class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {//存储wordDict 背包unordered_setstring wordMap(wordDict.begin(),wordDict.end());vectorint dp(s.size()1,false);//dp数组dp[0] true;//求的是排列数有顺序背包在外层for(int i 1;is.size();i){//遍历背包for(int j 0;ji;j){//遍历物品string tmp s.substr(j,i-j);if(wordMap.find(tmp)! wordMap.end()dp[j] true){dp[i] true;}}}return dp[s.size()];}
};【打家劫舍】
【198】打家劫舍
你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。
按照五部曲进行推导
class Solution {
public:int rob(vectorint nums) {int n nums.size();//确定dp数组 dp[i]存放最高金额vectorint dp(n);if(n 0)return 0;if(n 1)return nums[0];if( n 2)return max(nums[0],nums[1]);dp[0] nums[0];dp[1] max(nums[0],nums[1]);for(int i 2;in;i){dp[i] max(dp[i-1],nums[i]dp[i-2]);coutdp[i]endl;}return dp[n-1];}
};【213】
【337】
【子序列问题】
子序列包括连续、不连续、编辑距离、回文等等…
【300】最长子序列
1)根据返回值确定dp[i]:以nums[i]结尾的最长子序列的数组长度。
2)状态转移方程 if(nums[i]nums[j])dp[i] max(dp[i],dp[j]1);往前对比
3dp数组初始化dp[i] 1
(4) 确定遍历顺序dp[i1] dp[i]
class Solution {
public:int lengthOfLIS(vectorint nums) {int res 1;if(nums.size() 1)return 1;if(nums.size() 0)return 0;vectorint dp(nums.size(),1);for(int i 1;inums.size();i){for(int j 0;ji;j){if(nums[i]nums[j])dp[i] max(dp[i],dp[j]1);}if(dp[i]res)res dp[i];//不一定是最后一个元素取最长子序列}return res;}
};【301】
【152】乘积最大子数组
给你一个整数数组 nums 请你找出数组中乘积最大的非空连续子数组该子数组中至少包含一个数字并返回该子数组所对应的乘积。测试用例的答案是一个 32-位 整数。
注意这道题需要维护当前最小值存在负数让最大值变成最小值的情况。 1.确定dp数组和下标 本来是只想取dp[i]:以下标 i 结尾的连续子序列的乘积的最大值。 即可得dp[i] max(dp[i - 1] * nums[i], nums[i])但是如果nums[i]是负数的话会把最大值变化最小值。或者前面累乘的最小值会变成最大值。所以我们还要加一维去维护当前最小值 dp[i][0]:下标为i范围内的子数组最大乘积。 dp[i][1]:下标为i范围内的子数组最小乘积。 2.确定递推公式 if nums[i] 0dp[i][0] max(dp[i - 1][0] * nums[i], nums[i]);dp[i][1] min(dp[i - 1][1]* nums[i], nums[i]);else dp[i][0] max(dp[i - 1][1] * nums[i], nums[i]);dp[i][1] min(dp[i-1][0]*nums[i],nums[i]);3.确定初始化dp dp[0][1] nums[0] dp[0][0] nums[0] 4.初始化顺序 从左到右,从上到下 5.例举dp数组 输入: nums [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。
2263-2-124-48得到第一列最大值以后还要去选择其中最大的值进行输出
class Solution {
public:int maxProduct(vectorint nums) {vectorvectorint dp(nums.size(),vectorint(2,0));int m nums.size();dp[0][0] nums[0];dp[0][1] nums[0];for(int i 1;im;i){if(nums[i]0){dp[i][0] max(dp[i-1][0]*nums[i],nums[i]);dp[i][1] min(dp[i-1][1]*nums[i],nums[i]); }else{dp[i][0] max(dp[i-1][1]*nums[i],nums[i]);dp[i][1] min(dp[i-1][0]*nums[i],nums[i]); }}int res dp[0][0];for(int i 0;im;i){res max(dp[i][0],res);}return res;}
};
为了防止越界可以这样做用例[0,10,10,10,10,10,10,10,10,10,-10,10,10,10,10,10,10,10,10,10,0]
class Solution {
public:int maxProduct(vectorint nums) {int len nums.size();vectorlong long dpMax(len);vectorlong long dpMin(len);dpMax[0] nums[0];dpMin[0] nums[0];long long maxProduct dpMax[0];for (int i 1; i len; i) {long long tmp1 nums[i] * dpMin[i - 1];long long tmp2 nums[i] * dpMax[i - 1];if (tmp1 INT_MIN) {tmp1 INT_MIN;//钳住}if (tmp2 INT_MIN) {tmp2 INT_MIN;}dpMax[i] max(static_castlong long(nums[i]), max(tmp1, tmp2));dpMin[i] min(static_castlong long(nums[i]), min(tmp1, tmp2));maxProduct max(maxProduct, dpMax[i]);}return static_castint(maxProduct);}
};【718】最长重复子数组
多维动态规划
与图论的区别就是多维动态规划还是需要转移方程的。图论一般就是DFS和BFS直接做。 动态规划最开始做的时候为了便于理解都用二维dp数组方便理解
【62】不同路径
题目一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。 问总共有多少条不同的路径 解法1利用深搜(类似于深搜)由于只有两个方向可以枚举出来有多少种路径。注意题目中说机器人每次只能向下或者向右移动一步那么其实机器人走过的路径可以抽象为一棵二叉树而叶子节点就是终点
class Solution {
public:int dfs(int i,int j,int m,int n){if(im || jn)return 0;//边界条件if(i m-1 j n-1)return 1;//找到了一条路return dfs(i1,j,m,n) dfs(i,j1,m,n);//返回结果左边右边}int uniquePaths(int m, int n) {return dfs(0,0,m,n);//从(0,0)开始}
};假设是3*3列网格递归路径是 (0, 0)/ \(1, 0) (0, 1)/ \ / \(2, 0) (1, 1) (1, 1) (0, 2)/ \ / \ / \ / \超出边界 (2, 1) (2, 1) (1, 2) (1, 2)/ \ / \ / \ / \超出边界 (2, 2) (2, 2) 超出边界 (2, 2)/ / \ \终点 终点 终点 终点
但是这种方法会超时因为这个树的深度是mn-1,这棵树的深度其实就是mn-1深度按从1开始计算。那二叉树的节点个数就是 2^(m n - 1) - 1。可以理解深搜的算法就是遍历了整个满二叉树其实没有遍历整个满二叉树只是近似而已。 所以上面深搜代码的时间复杂度为O(2^(m n - 1) - 1)可以看出这是指数级别的时间复杂度是非常大的。
解法2动态规划 1确定dp数组以及下标的含义 dp[i][j] :[0][0]到坐标[i][j]共有dp[i][j] 条不同的路径。 2确定dp状态转移公式 想想dp[i][j]上一个状态是什么分别是dp[i-1][j]和dp[i][j-1] dp[i-1][j]表示[0][0]到坐标[i][j]共有dp[i-1][j]条不同的路径dp[i][j-1]表示[0][0]到坐标[i][j-1]共有dp[i][j-1]条不同的路径 所以可以明确dp[i][j] dp[i-1][j]dp[i][j-1] 3dp数组如何初始化 dp[i][0] 1,从[0][0]到[i][0]的路径只有1条 dp[0][j] 1,从[0][0]到[0][j]的路径只有1条
for(int i 0;im;i)dp[i][0]1;
for(int j 0;jn;j)dp[0][j]1;4确定遍历顺序 dp[i][j] dp[i-1][j]dp[i][j-1],从左到右从上到下遍历保证推导dp[i][j]的时候dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的。 5举例推导dp数组按照3*3的表格为例子则最后一个dp[m-1][n-1]就是最后返回的6条不同路径。
坐标012011111232136
class Solution {
public:int uniquePaths(int m, int n) {vectorvectorint dp(m,vectorint(n,0));//进行初始化for(int i 0;im;i)dp[i][0] 1;for(int j 0;jn;j)dp[0][j] 1;//确定遍历顺序从左到右从上到下for(int i 1;im;i){for(int j1;jn;j){dp[i][j] dp[i-1][j]dp[i][j-1];}}return dp[m-1][n-1];}
};时间复杂度O(m × n)空间复杂度O(m × n) 用一维滚动数组可以降低空间复杂度为O( n)但是对于不熟悉的题型还是老老实实用二维数组做吧。
【64】最小路径和
给定一个包含非负整数的 m x n 网格 grid 请找出一条从左上角到右下角的路径使得路径上的数字总和为最小。 说明每次只能向下或者向右移动一步。 (1)确定dp数组以及下标含义 dp[i][j]:从[0][0]到[i][j]的最小路径数字总和。 (2)确定递推公式 dp[i][j]只能从dp[i-1][j]和dp[i][j-1]这两个方向获得并且要获得最小路径数字总和。d[i][j] grid[i][j]min{dp[i-1][j],dp[i][j-1]} (3)初始化dp数组 第一行和第一列都只有一种走法则d[i][0]和dp[0][j]直接累加在一起就行。 for(int i 1;im;i) dp[i][0] grid[i][0] dp[i-1][0]; for(int j 1;jn;j) dp[0][j] grid[0][j] dp[0][j-1]; (4)遍历顺序 从上到下从左到右 (5)举例dp数组
坐标012014512862687
class Solution {
public:int minPathSum(vectorvectorint grid) {int m grid.size();int n grid[0].size();vectorvectorint dp(m,vectorint(n,0));dp[0][0] grid[0][0];for(int i 1;im;i) dp[i][0] grid[i][0] dp[i-1][0];for(int j 1;jn;j) dp[0][j] grid[0][j] dp[0][j-1];for(int i 1; im;i){for(int j 1;jn;j){dp[i][j] grid[i][j] min(dp[i][j-1], dp[i-1][j]);}}return dp[m-1][n-1];}
};
【647】回文子串
给你一个字符串 s 请你统计并返回这个字符串中 回文子串 的数目。回文字符串 是正着读和倒过来读一样的字符串。子字符串 是字符串中的由连续字符组成的一个序列。 本题可以用双指针法做也可以用动规做动规的空间复杂度高一点。 1确定dp数组以及下标的含义 这道题如果dp[i] 为 下标i结尾的字符串有 dp[i]个回文串的话。很难去判断递推关系dp[i] 和 dp[i-1] dp[i 1] 看上去都没啥关系。 但是我们假设知道了一个子串是回文子串的话比如在[i,j]内是回文子串再去看[i-1]和[j1]是否相等就知道是否是回文子串换句话说判断一个子字符串字符串的下表范围[i,j]是否回文依赖于子字符串下表范围[i 1, j - 1] 是否是回文。 dp[i] [j]表示区间范围[i,j]的子串是否回文dp[i] [j] true表示回文dp[i] [j] false表示非回文。 2确定dp状态转移公式 要讨论dp[i1][j-1]的状态 if(s[i] s[j]){if(j-i1){//a aadp[i] [j] true;res;}else{//a bbc aif(dp[i1][j-1]){//子串要是回文的s才是回文dp[i] [j] true;res}}}else{dp[i] [j] false;}3dp数组如何初始化 dp[i][j] false 4确定遍历顺序 由于这里的dp[i1][j-1]会决定dp[i][j]所以遍历顺序应该是从下到上从左到右。 5举例推导dp数组 以aaa为例子因为[i,j]是一个区间则说明ij,二维数组下半部分全部是false不需要管 | 坐标 | 0 | 1 | 2 | | ---- | ---- | ---- | ---- | | 0| 1 | 1 |1 | | 1| 0 | 1 | 1 | | 2 | 0 | 0 | 1 | 本题的难点是要把从数组区间上的[i][j]抽象到二维数组上并且初始化顺序和递推公式都有变化。
class Solution {
public:int countSubstrings(string s) {int m s.size();int res 0;vectorvectorbool dp(m,vectorbool(m,false));//优化ij 所以二维数组下半部分都不用遍历了for(int i m-1;i0;i--){for(int j i; j m;j){if(s[i] s[j]){if(j-i1){//a aadp[i][j] true;res;}else{if(dp[i1][j-1]){//这里是区间上的[i][j]dp[i][j] true;res;}}}else{dp[i][j] false;}}} return res;}
};时间复杂度on^2空间复杂度o(n ^2)。
【5】最长回文子串
给你一个字符串 s找到 s 中最长的 回文子串。 跟【647】差不多如果是回文子串就是要给一个变量maxlength去判断是不是最长的回文子串
class Solution {
public:string longestPalindrome(string s) {int m s.size();int maxlen 0;int left 0;vectorvectorbool dp(m,vectorbool(m,false));//从下到上从左到右 [i,j]for(int i m-1;i0;i--){for(int j i;j m;j){if(s[i] s[j]){if(j-i1){dp[i][j] true;}else if(dp[i1][j-1]){dp[i][j] true;}}else{dp[i][j] false;}//处理最长回文子串if(dp[i][j] j-i1maxlen){maxlen j-i1;left i;}}}return s.substr(left,maxlen);}
};【1143】最长公共子序列
与【718】最长重复子数组一起做。 给定两个字符串 text1 和 text2返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 返回 0 。一个字符串的 子序列 是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。例如“ace” 是 “abcde” 的子序列但 “aec” 不是 “abcde” 的子序列。两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。(没有指定方向)
注意“oxcpqrsvwf”“shmtulqrypy” 最长是qr要是单独遍历这么做还要去存储。
本来以为可以用遍历的方式做的但是还要考虑的是求的是**最长公共子序列一是要最长二是要双向。**遍历的方式就有点复杂了。 这里的子序列要求有相对顺序可以不连续。 利用动态规划 (1)确定dp数组以及下标的含义 dp[i][j] :长度为[0,i]的字符串text1和[0,j]的字符串text2的最长公共子序列个数; (2) 递推公式 主要就是两大情况 text1[i] 与 text2[j]相同text1[i] 与 text2[j ]不相同 text1[i] 与 text2[j]相同:找到公共元素dp[i][j] dp[i-1][j-1]1; text1[i] 与 text2[j]不相同dp[i][j] max(dp[i - 1][j], dp[i][j - 1]); (3)dp数组初始化 dp[i][j] 0; (4)dp数组遍历顺序 从递推公式可以看有三个方向可以推导出dp[i][j]:从左到右从上到下 遇到的问题当我想初始化的时候第一行和第二行需要先初始化但是他们的初始化又要单独去遍历判断赋值不如重新给dp[i][j]意义表示第0-i-1的子序列和0-j-1的子序列这样的话就可以减轻我们初始化的负担 text1[i] 与 text2[j]也要随即向前移一个这样才能判断[0][0]下面的图可以很明确第一行表示空字符和text2比较肯定为0同理第一列。 class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int m text1.size();int n text2.size();vectorvectorint dp(m1,vectorint(n1,0));for(int i 1;im1;i){for(int j 1;jn1;j){if(text1[i-1] text2[j-1]){//从0开始判断dp[i][j] dp[i-1][j-1] 1;}else{dp[i][j] max(dp[i-1][j],dp[i][j-1]); }}}return dp[m][n];}};【72】 编辑距离
给你两个单词 word1 和 word2 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作 插入一个字符 删除一个字符 替换一个字符
利用动态规划 (1)确定dp数组以及下标的含义 dp[i][j] :长度为[0,i-1]的字符串word1和[0,j-1]的字符串word2的编辑距离操作数。 (2) 递推公式 在确定递推公式的时候要考虑编辑的操作
if(word1[i-1] word2[j-1]){
//donothing dp[i][j] dp[i-1][j-1];
}else{
//需要编辑距离
//增加//word2添加一个元素,相当于word1删除一个元素dp[i][j] dp[i-1][j]1;
//删除//word2删除一个元素dp[i][j] dp[i][j-1]1;
//换dp[i][j] dp[i-1][j-1]1;
//只要求这三个的最小值就行了dp[i][j] min(dp[i-1][j]1,dp[i][j-1]1,dp[i-1][j-1]1);
}word2添加一个元素相当于word1删除一个元素例如 word1 ad word2 aword1删除元素d 和 word2添加一个元素d变成word1a, word2ad 最终的操作数是一样 dp数组如下图所示意的 a a d---------- ---------------| 0 | 1 | | 0 | 1 | 2 |---------- ---------------a | 1 | 0 | a | 1 | 0 | 1 |---------- ---------------d | 2 | 1 |----------(3)dp数组初始化 dp[i][j] 表示以下标i-1为结尾的字符串word1和以下标j-1为结尾的字符串word2最近编辑距离为dp[i][j]。 那么dp[i][0] 和 dp[0][j] 表示什么呢 dp[i][0] 以下标i-1为结尾的字符串word1和空字符串word2最近编辑距离为dp[i][0]。 那么dp[i][0]就应该是i对word1里的元素全部做删除操作即dp[i][0] i; 同理dp[0][j] j; (4)dp数组遍历顺序 从递推公式可以看有三个方向可以推导出dp[i][j]:从左到右从上到下:
class Solution {
public:int minDistance(string word1, string word2) {int m word1.size();int n word2.size();vectorvectorint dp(m1,vectorint(n1,0));//空字符直接删除操作数就是字符长度for (int i 0; i word1.size(); i) dp[i][0] i;//删除word1for (int j 0; j word2.size(); j) dp[0][j] j;//删除word2for(int i 1;im1;i){for(int j 1;jn1;j){if(word1[i-1] word2[j-1]){//什么都不做dp[i][j] dp[i-1][j-1];}else{//进行增删换三种操作//删除word1//删除word2(增加word1)//替换word1或者word2dp[i][j] min({dp[i-1][j]1,dp[i][j-1]1,dp[i-1][j-1]1});}}}return dp[m][n];}
};字符类的都可以考虑多构造一行一列来存放空字符。
