动态规划经典例题详解

时间：2025-02-23 08:04:43

最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

解题思路

运用的是动态规划的思想，由于是求最长回文字符串。
dp数组定义为：在子串s[i…j]中，最长回文子序列的长度为dp[i][j];
子问题： 所以其子问题可以看作是求短一点长度，例如求dp[i][j],可 以由求其子问题dp[i+1][j-1]的结果算出。所以其子问题即是长度 减去左右两端的字符串的长度。
递推公式: dp[i][j] = dp[i+1][j-1] + 2 s[i] == s[j]
dp[i][j] = max(dp[i+1][j],dp[i][j+1]) s[i] != s[j]

伪代码

getLength(str):
输入： 一个字符串
输出： 字符串内最长回文字符串的长度
for i <-- length - 1 to 0 do:
	dp[i][i] = 1; 
	for j <-- i+1 to length -1 do:
 		If(str[i] == str[j]) then:
       		dp[i][j] = dp[i+1][j-1]+2;
    	else
      		dp[i][j] = max(dp[i+1][j],dp[i][j+1])
    end
end
return dp[0][len-1];

最长递增子序列

给你一个整数数组 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

思路

思路1二分查找：

二分查找的算法，属于是分治法的一种思想，将从头到尾的遍历整个数组，然后将其分成若干堆，每一堆只能从大到小排列。二分查找的目的就是找到当前的数放进去的堆，然后把数组的那个位置的数换成当前的数，如果没有找到比当前数大的堆，只能新开一个堆，这样，便能保证有几个堆，就是最长子序列的长度

思路2 ： 动态规划，

Α：求解数组的最长递增子序列，可以看成由他短一点是数组的最长上升子序列经过某种计算得到。
Β：可以定义一个一维数组dp[i]代表数组前i项的最长上升子序列长度。
C: 边界条件是：dp[i]的初始值为1，所以求解其最长的长度即是求dp[i]的前 i项最长的，可以使用循环从0–i中求最大值。
如果j<i,并且 nums[i]>nums[j],则dp[i] = max(dp[i],dp[j]+1)
D: 递推式：dp[i] = max(dp[j]) + 1 其中 0 =< j < i且 num[j] < num[i]
dp最大值为max(dp[i]);

伪代码

  1. 二分查找
getMaxBySearch(nums[0....n-1]):
输入： nums[0...n-1]数组
输出：数组中最长子序列的长度sum和最长子序列的数top数组
top[n]    //初始化一个堆数组 
sum      //初始化最初的数量
for i <-- 0 to n-1 do:
  num = nums[i];    //要操作的数值
  Left = 0;right = sum
   while(left < right) do
      mid = (left+right) >> 1
     If (top[mid] > num) then
        right  = mid;
      else if(top[mid] < num)
      left  = mid+1;
    else
      right = mid;
    end
 end
If(left == sum) then //说明没有找到自己的堆，另起重建一堆
   sum++;
end
top[left] = num
return  sum and top[]
  1. 动态规划
 Getlength(nums[0...n-1]):
输入：nums[0....n-1]数组
输出：数组中最长子序列的长度sum
for i <-- 1 to n-1 do:
	dp[i] = 1
	Maxlength = 1
	for  j <-- 0 to i do
		If(nums[i] > nums[j])
  			 dp[i] = max(dp[i],dp[j]+1)
		end
	Maxlength = max(dp[i],Maxlength)
return MaxLength;

最长等差子序列

给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。
子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。
示例 1：
输入：arr = [1,2,3,4], difference = 1
输出：4
解释：最长的等差子序列是 [1,2,3,4]。

思路

  1. 本题用了动态规划的思路。其子问题可以看作遍历数组每个元素，求每个元素的之前序列的最长等差序列的长度，最后合并。
  2. 定义一个dp，用来存储每个元素的最长等差序列的长度。当每个元素从0—>i遍历的时候，如果0<j<i时，并且nums[j] = nums[i]-d，则dp[i] = dp[j]+1;
    也可以换成当遍历到nums[i]的时候，在其map集合里面康康有没有nums[i]-difference，如果没有则设为一，如果有则继续加一。
    所以此问题的递推状态方程即是dp[v] = dp[v-d]+1。

伪代码

getLogestSubSequence(nums[0....n-1]);
输入：一个数组nums[0....n-1]
输出：数组中最长递增子序列的长度
Map dp   //定义一个map集合
maxLength = 1  //定义最大值，初始化为1
for i <-- 0 to n-1 do:
	num = nums[i]
	If(map.get(num)) then:
		map.put(num, map.get(num)+1)
	else:
		map.put(num,1);
    end
maxLength = max(map.get(num),maxLength);
return maxLength;

最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

思路

  1. 本题用了动态规划的思路。其子问题可以看作遍历两个序列的长度，i是遍历text1的游标，j是text2的游标，i和j的最大公共子序列可以由他小于i和小于j的最长长度得到。
  2. 定义一个dp二维数组，由于是两个字符串进行比较，所以设计为一个二维数组，每个dp[i][j]表示text1的前i个和text2的前j个的最长公共子序列长度。
  3. 边界情况是当i=0或者j= 0时候，dp[i][j]均为0.递推关系如下。
    ①当text1[i]==text[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]);

伪代码

longestComonSubsequence(text1,text2):
输入：两个字符串text1和text2
输出：公共字符串的长度len
dp[len1+1][len2+1]   / /初始化dp数组
for i <-- 1 to len1 do
  for j  <--- 1 to len2 do
      If(text1[i] == text2[j]) then
         dp[i][j] = dp[i-1][j-1]+1;
      else
        dp[i][j] = max(dp[i-1][j],dp[i][j-1])
     End
   end
end
return dp[len1][len2];

最优编辑距离

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符

思路

①本题用了动态规划的思路。本题看起来比较复杂。可以先由暴力解法逐步过度到动态规划思路。可以考虑使用两个指针i，j分别从s1和s2的最后往前游走，假如s1[i] == s2[j],这时候就直接跳过，i和j游标均往前移动。继续比较。
如果s[i] ≠ s[j] ,这时候需要去选择操作，因为操作只有三种，要么插入，删除或者替换。所以可以写出模板

If s1[i] == s2[j]
		Skip, i和 j均往前移动
else
	三选一：插入/删除/替换

②定义一个dp二维数组，由于是两个字符串进行比较，所以确定是二维数组，二维数组的定义为dp[i][j]表示s1的前i子串变成s2的前j的子串需要的最少步数
③所以边界情况可以看得出当s1为空串时dp[0][j] = j,当s2为空串时dp[i][0] = i;
④下面研究几种操作，
Α： 当插入操作时，由于插入s1，则直接可以跟j中元素匹配，所以i游标 不变，j游标需要往前移动一格，所以dp[i][j] = dp[i][j-1]+1；
Β: 当删除操作时，由于删除s1中的i标元素，所以将i游标直接往前移动 一个变为i-1，继续让i-1和j进行匹配。所以dp[i][j] = dp[i-1][j]+1;
Θ: 当进行替换操作时，由于s1的i处被替换成和j相同的字符，此时已经
匹配，所以只需要i，j同时前移。所以dp[i][j] = dp[i-1][j-1]+1;
⑤ 所以dp[i][j]和其左上角，上面，左面的有关，选择最小的一个进行操作。从 而可以画出其dptable。

伪代码

minDistance(s1,s2):
输入：两个字符串text1和text2
输出：由text1变成text2所需要的最少的步数
m  = len(s1);
n  =  len(s2)
dp[m+1][n+1]    //初始化dp数组
//base case 边界条件
for i <-- 1 to m do
  dp[i][0] = i
for j <-- 1 to n do
   dp[0][j] = j
for i <-- 1 to len1 do
   for j <-- 1 to len2 do
     	If (s1[i] == s2[j]) then 
			dp[i][j] = dp[i-1][j-1];
		else 
   			dp[i][j] = min(dp[i][j-1]+1,dp[i-1][j]+1,dp[i-1][j-1]+1);
		end
	end
end
return dp[m][n];

相关文章