devbox
Monodyee
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法策略 - 动态规划_策略算法

作者：Monodyee | 2024-06-14 05:24:30

赞

踩

策略算法

目录

动态规划（Dynamic Programming）

动态规划的常规步骤

动态规划的一些相关概念

无后效性

有后效性

算法1 – 找零钱

问题

状态定义

题解 – 暴力递归

题解 – 记忆化搜索

题解 – 递推

思考题: 请输出找零钱的具体方案 (具体是用了哪些面值的硬币)

题解 – 通用实现优化

算法2 – 最大连续子序列和

问题

状态定义

状态转移方程和初始状态

题解 – 动态规划 – 实现

题解 – 动态规划 – 优化实现

算法3 – 最长上升子序列 (LIS)

问题

状态定义

状态转移方程

题解 – 动态规划 – 实现

题解 – 耐心排序 – 思路

题解 – 耐心排序 – 实现

题解 – 耐心排序 – 二分搜索 – 思路

题解 – 耐心排序 – 二分搜索 – 实现

算法4 – 最长公共子序列 (LCS)

问题

思路

题解 – 递归实现

递归实现分析

题解 – 非递归实现

题解 – 非递归实现 – 滚动数组优化

题解 – 非递归实现 – 一维数组优化

题解 – 非递归实现 – 一维数组优化 –  空间复杂度优化

算法5 – 最长公共子串

问题

思路

题解 – 实现

题解 – 一维数组优化

题解 – 一维数组优化 – 空间复杂度优化

题解 – 一维数组优化 – 空间复杂度优化 – 逆序优化

算法6 – 0-1背包

问题

题解 – 实现 – 二维数组

题解 – 实现 – 一维数组 – 倒序优化

题解 – 实现 – 循环优化

0-1背包 – 恰好装满

问题

思路

实现

动态规划（Dynamic Programming）

动态规划，简称DP, 是求解最优化问题的一种常用策略
通常的使用规则 (一步一步优化)

  1. 暴力递归 (自顶向下，出现了重叠子问题)
  2. 记忆化搜索 (自顶向下)
  3. 递推 (自底向上)

动态规划的常规步骤

动态规划中的 “动态” 可以理解为是“会变化的状态”

  1. 定义状态 (状态是原问题、子问题的解)  比如定义 dp(i) 的含义
  2. 设置初始状态 (边界)  比如设置 dp(0) 的值
  3. 确定状态转移方程  比如确定 dp(i) 和 dp(i – 1) 的关系, 即已知dp(i-1), 如果推算出dp(i) 或者已知dp(i), 如何推算出dp(i-1) 

动态规划的一些相关概念

来自维基百科的解释: Dynamic Programming is a method for solving a complex problem by breaking it down into a  collection of simpler subproblems, solving each of those subproblems just once, and storing their  solutions.

  1. 将复杂的原问题拆解成若干个简单的子问题
  2. 每个子问题仅仅解决1次，并保存它们的解
  3. 最后推导出原问题的解

可以用动态规划来解决的问题，通常具备2个特点:
(1) 最优子结构(最优化原理): 通过求解子问题的最优解, 可以获得原问题的最优解
(2) 无后效性
       a. 某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响（未来与过去无关）
       b. 在推导后面阶段的状态时，只关心前面阶段的具体状态值，不关心这个状态是怎么一步步推导出来的

无后效性

问题: 从起点(0, 0)走到终点(4, 4)一共有多少种走法？只能向右、向下走

 
假设 dp(i, j) 是从(0, 0)走到(i, j)的走法:
     dp(i, 0) = dp(0, j) = 1
     dp(i, j) = dp(i, j – 1) + dp(i – 1, j)

无后效性: 推导 dp(i, j) 时只需要用到 dp(i, j – 1)、dp(i – 1, j) 的值, 不需要关心 dp(i, j – 1)、dp(i – 1, j) 的值是怎么求出来的

有后效性

问题: 从起点(0, 0)走到终点(4, 4)一共有多少种走法？可以向左、向右、向上、向下走，但是同一个格子不能走 2 次

有后效性: dp(i, j) 下一步要怎么走，还要关心上一步是怎么来的, 也就是还要关心 dp(i, j – 1)、dp(i – 1, j) 是怎么来的？因为, 每个格子只能走1次, 那么在dp(i, j)后面的步骤中需要考虑dp(i, j)前面的步骤, 不能重复走同一个格子

算法1 – 找零钱

LeetCode: leetcode_322_零钱兑换

问题

假设有25分、20分、5分、1分的硬币，现要找给客户41分的零钱，如何办到硬币个数最少？
此前用贪心策略得到的并非是最优解 (贪心得到的解是 5 枚硬币)

状态定义

假设 dp(n) 是凑到 n 分需要的最少硬币个数

  •   如果第 1 次选择了 25 分的硬币，那么 dp(n) = dp(n – 25) + 1
  •   如果第 1 次选择了 20 分的硬币，那么 dp(n) = dp(n – 20) + 1
  •   如果第 1 次选择了 5 分的硬币，那么 dp(n) = dp(n – 5) + 1
  •   如果第 1 次选择了 1 分的硬币，那么 dp(n) = dp(n – 1) + 1

所以 dp(n) = min { dp(n – 25), dp(n – 20), dp(n – 5), dp(n – 1) } + 1

题解 – 暴力递归

  1. /**
  2.  * 暴力解决
  3.  * @param n
  4.  * @return
  5.  */
  6. static int coinChange(int n){
  7.     if(n <= 0) return Integer.MAX_VALUE;
  8.     if (n == 25 || n == 20 || n == 5 || n == 1) return 1;
  9.     /**
  10.      * 找一枚硬币, 剩下零钱需要最少的硬币数量
  11.      * 当前找的这枚硬币可以是25, 20, 5, 1;
  12.      */
  13.     int min1 = Math.min(coinChange(n - 25),coinChange(n - 20));
  14.     int min2 = Math.min(coinChange(n - 5),coinChange(n - 1));
  15.     //确认找哪种硬币后, 总找硬币数量加一
  16.     return Math.min(min1,min2) + 1;
  17. }

类似于斐波那契数列的递归版，会有大量的重复计算，时间复杂度较高

题解 – 记忆化搜索

  1. /**
  2.  * 记忆化搜索
  3.  */
  4. static int coinChange1(int n){
  5.     if(n < 1) return -1;
  6.     int[] coins = new int[n + 1];
  7.     for (int i = 0; i < coins.length; i++) {
  8.         if(i == 25) coins[i] = 1;
  9.         if(i == 20) coins[i] = 1;
  10.         if(i == 5) coins[i] = 1;
  11.         if(i == 1) coins[i] = 1;
  12.     }
  13.     return coinChange1(n,coins);
  14. }
  15.  
  16. static int coinChange1(int n, int[] coins){
  17.     if(n <= 0) return Integer.MAX_VALUE;
  18.     //如果待找零钱的最少硬币数量已计算出来, 则直接返回
  19.     if(coins[n] != 0) return coins[n];
  20.     /**
  21.      * 找一枚硬币, 剩下零钱需要最少的硬币数量
  22.      * 当前找的这枚硬币可以是25, 20, 5, 1;
  23.      */
  24.     int min1 = Math.min(coinChange1(n - 25,coins),coinChange1(n - 20,coins) );
  25.     int min2 = Math.min(coinChange1(n - 5,coins),coinChange1(n - 1,coins) );
  26.     //当前零钱已确认找哪种硬币后, 总找硬币数量加一, 并且暂存于在数组中
  27.     coins[n]  = Math.min(min1,min2) + 1;
  28.     return coins[n];
  29. }

题解 – 递推

  1. /**
  2.  * 递推
  3.  * @param n
  4.  * @return
  5.  */
  6. static int coinChange3(int n){
  7.     if(n <= 0) return Integer.MAX_VALUE;
  8.     int[] coins = new int[n+1];
  9.     for (int i = 1; i <= n; i++) {
  10.         int min = Integer.MAX_VALUE;
  11.         if(i >= 1) min = Math.min(min,coins[i - 1]);
  12.         if(i >= 5) min = Math.min(min,coins[i - 5]);
  13.         if(i >= 20) min = Math.min(min,coins[i - 20]);
  14.         if(i >= 25) min = Math.min(min,coins[i - 25]);
  15.         coins[i] = min + 1;
  16.     }
  17.     return coins[n];
  18. }

思考题: 请输出找零钱的具体方案 (具体是用了哪些面值的硬币)

  1. /**
  2.  * 递推
  3.  * @param n
  4.  * @return
  5.  */
  6. static int coinChange3(int n){
  7.     if(n <= 0) return Integer.MAX_VALUE;
  8.     int[] coins = new int[n+1];
  9.     //faces[i]是凑够i分时最后那枚硬币的面值
  10.     int[] faces = new int[coins.length];
  11.     for (int i = 1; i <= n; i++) {
  12.         int min = Integer.MAX_VALUE;
  13.         if(i >= 1){
  14.             min = Math.min(min,coins[i - 1]);
  15.             faces[i] = 1;
  16.         }
  17.         if(i >= 5){
  18.             min = Math.min(min,coins[i - 5]);
  19.             faces[i] = 5;
  20.         }
  21.         if(i >= 20){
  22.             min = Math.min(min,coins[i - 20]);
  23.             faces[i] = 20;
  24.         }
  25.         if(i >= 25){
  26.             min = Math.min(min,coins[i - 25]);
  27.             faces[i] = 25;
  28.         }
  29.         coins[i] = min + 1;
  30.         print(faces,i);
  31.     }
  32.     return coins[n];
  33. }
  34.  
  35. static void print(int[] faces, int n){
  36.     System.out.print("零钱:"+n+", 应找硬币:");
  37.     while(n > 0){
  38.         //输出凑够n分时,所需要的硬币面值
  39.         System.out.print(faces[n] + " ");
  40.         //计算凑够剩下零钱所需要的硬币
  41.         n -= faces[n];
  42.     }
  43.     System.out.println();
  44. }

题解 – 通用实现优化

  1. static int coinChange4(int n, int[] faces){
  2.     if(n <= 0) return Integer.MAX_VALUE;
  3.     int[] coins = new int[n+1];
  4.     for (int i = 1; i <= n; i++) {
  5.         int min = Integer.MAX_VALUE;
  6.         for (int face : faces) {
  7.             if(i < face) continue;
  8.             if(coins[i-face] < 0) continue;  //如果使用面值为face的硬币后, 剩余的零钱无法找到合适的硬币, 那么当前零钱也无法找回
  9.             min = Math.min(coins[i - face], min);
  10.         }
  11.         //如果i没有找到合适的硬币, 那么返回-1
  12.         if (min == Integer.MAX_VALUE){
  13.             coins[i] = -1;
  14.         }else{
  15.             coins[i] = min + 1;
  16.         }
  17.     }
  18.     return coins[n];
  19. }

算法2 – 最大连续子序列和

问题

给定一个长度为 n 的整数序列，求它的最大连续子序列和
比如 –2、1、–3、4、–1、2、1、–5、4 的最大连续子序列和是 4 + (–1) + 2 + 1 = 6

状态定义

假设 dp(i) 是以 nums[i] 结尾的最大连续子序列和（nums是整个序列）

  • 以 nums[0] –2 结尾的最大连续子序列是 –2，所以 dp(0) = –2
  • 以 nums[1] 1 结尾的最大连续子序列是 1，所以 dp(1) = 1
  • 以 nums[2] –3 结尾的最大连续子序列是 1、–3，所以 dp(2) = dp(1) + (–3) = –2
  • 以 nums[3] 4 结尾的最大连续子序列是 4，所以 dp(3) = 4
  • 以 nums[4] –1 结尾的最大连续子序列是 4、–1，所以 dp(4) = dp(3) + (–1) = 3
  • 以 nums[5] 2 结尾的最大连续子序列是 4、–1、2，所以 dp(5) = dp(4) + 2 = 5
  • 以 nums[6] 1 结尾的最大连续子序列是 4、–1、2、1，所以 dp(6) = dp(5) + 1 = 6
  • 以 nums[7] –5 结尾的最大连续子序列是 4、–1、2、1、–5，所以 dp(7) = dp(6) + (–5) = 1
  • 以 nums[8] 4 结尾的最大连续子序列是 4、–1、2、1、–5、4，所以 dp(8) = dp(7) + 4 = 5

状态转移方程和初始状态

状态转移方程
    如果 dp(i – 1) ≤ 0，那么 dp(i) = nums[i]
    如果 dp(i – 1) > 0，那么 dp(i) = dp(i – 1) + nums[i]

初始状态
    dp(0) 的值是 nums[0]

最终的解
    最大连续子序列和是所有 dp(i) 中的最大值 max { dp(i) }，i ∈ [0, nums.length)

题解 – 动态规划 – 实现

  1. /**
  2.  * 最大连续子序列
  3.  * 示例: {–2, 1, –3, 4, –1, 2, 1, –5, 4 }
  4.  */
  5. static int maxSubArray(int[] nums){
  6.     if(nums == null || nums.length == 0) return 0;
  7.     int[] dp = new int[nums.length];
  8.     int max = dp[0] = nums[0]; //以dp[0]结尾的最大子序列的值为nums[0], max默认为dp[0]
  9.     for (int i = 1; i < nums.length; i++) {
  10.         /**
  11.          * 如果以dp[i-1]结尾的最大子序列的值大于0, 那么以dp[i]结尾的最大子序列为: 以dp[i-1]结尾的最大子序列 + nums[i];
  12.          * 否则, 以dp[i]结尾的最大子序列为: nums[i]
  13.          */
  14.         if(dp[i-1] > 0){
  15.             dp[i] = dp[i-1] + nums[i];
  16.         }else{
  17.             dp[i] = nums[i];
  18.         }
  19.         max = Math.max(max,dp[i]);
  20.     }
  21.     return max;
  22. }

空间复杂度:O(n), 时间复杂度: O(n)

题解 – 动态规划 – 优化实现

  1. /**
  2.  * 最大连续子序列 -- 优化
  3.  *   仅使用dp变量, 而不是数组; dp为以nums[i-1]结尾的最大子序列的值
  4.  *
  5.  * 示例: {–2, 1, –3, 4, –1, 2, 1, –5, 4 }
  6.  */
  7. static int maxSubArray2(int[] nums){
  8.     if(nums == null || nums.length == 0) return 0;
  9.     int dp = nums[0];
  10.     int max = dp; //以dp[0]结尾的最大子序列的值为nums[0], max默认为dp[0]
  11.     for (int i = 1; i < nums.length; i++) {
  12.         /**
  13.          * 如果以nums[i-1]结尾的最大子序列(原dp)的值大于0, 那么以nums[i]结尾的最大子序列(新dp)为: 以nums[i-1]结尾的最大子序列(原dp) + nums[i];
  14.          * 否则, 以nums[i]结尾的最大子序列(新dp)为: nums[i]
  15.          */
  16.         if(dp > 0){
  17.             dp = dp + nums[i];
  18.         }else{
  19.             dp = nums[i];
  20.         }
  21.         max = Math.max(max,dp);
  22.     }
  23.     return max;
  24. }

空间复杂度: O(1), 时间复杂度: O(n)

算法3 – 最长上升子序列 (LIS)

最长上升子序列 (最长递增子序列, Longest Increasing Subsequence, LIS)

LeetCode: leetcode_300_最长上升子序列

问题

给定一个无序的整数序列，求出它最长上升子序列的长度 (要求严格上升)
比如 [10, 2, 2, 5, 1, 7, 101, 18] 的最长上升子序列是 [2, 5, 7, 101]、[2, 5, 7, 18]，长度是 4

状态定义

假设数组是 nums， [10, 2, 2, 5, 1, 7, 101, 18]
dp(i) 是以 nums[i] 结尾的最长上升子序列的长度，i ∈ [0, nums.length)

  • 以 nums[0] 10 结尾的最长上升子序列是 10，所以 dp(0) = 1
  • 以 nums[1] 2 结尾的最长上升子序列是 2，所以 dp(1) = 1
  • 以 nums[2] 2 结尾的最长上升子序列是 2，所以 dp(2) = 1
  • 以 nums[3] 5 结尾的最长上升子序列是 2、5，所以 dp(3) = dp(1) + 1 = dp(2) + 1 = 2
  • 以 nums[4] 1 结尾的最长上升子序列是 1，所以 dp(4) = 1
  • 以 nums[5] 7 结尾的最长上升子序列是 2、5、7，所以 dp(5) = dp(3) + 1 = 3
  • 以 nums[6] 101 结尾的最长上升子序列是 2、5、7、101，所以 dp(6) = dp(5) + 1 = 4
  • 以 nums[7] 18 结尾的最长上升子序列是 2、5、7、18，所以 dp(7) = dp(5) + 1 = 4

最长上升子序列的长度是所有 dp(i) 中的最大值 max { dp(i) }，i ∈ [0, nums.length)

状态转移方程

遍历 j ∈ [0, i)
1. 当 nums[i] > nums[ j]
      nums[i] 可以接在 nums[ j] 后面，形成一个比 dp( j) 更长的上升子序列，长度为 dp( j) + 1
      dp(i) = max { dp(i), dp( j) + 1 }
2. 当 nums[i] ≤ nums[ j]
      nums[i] 不能接在 nums[ j] 后面，跳过此次遍历（continue）
3. 状态的初始值
      dp(0) = 1
      所有的 dp(i) 默认都初始化为 1

题解 – 动态规划 – 实现

  1. /**
  2.  * 最长上升子序列 -- 动态规划
  3.  * 示例:{10, 2, 3, 5, 1, 7, 101, 18}
  4.  */
  5. static int lis(int[] nums){
  6.     if(nums == null || nums.length == 0) return 0;
  7.  
  8.     int[] dp = new int[nums.length];
  9.     int max = dp[1] = 1;
  10.     for (int i = 0; i < nums.length; i++) {
  11.         dp[i] = 1;
  12.         /**
  13.          * 每个nums[i]都需要跟前[0,i)范围内的所有以nums[j]结尾的最长上升子序列(dp[i])进行比较,
  14.          *   如果nums[i]的值大于nums[j], 那么以nums[i]结尾的最长上升子序列为: 以nums[j]结尾的最长上升子序列(dp[i]) + 1;
  15.          *   否则,以nums[i]结尾的最长上升子序列为:nums[i];
  16.          *
  17.          *   在计算以nums[i]的最长上升子序列时, 需要比较当前已计算出的dp[i]与dp[j]+1的大小, 取较大值
  18.          */
  19.         for (int j = 0; j < i; j++) {
  20.             if(nums[i] > nums[j]){
  21.                 //例: Math.max(dp[5],dp[3] + 1) 注意此时dp[5] = dp[2] + 1;
  22.                 dp[i] = Math.max(dp[i],dp[j] + 1);
  23.             }
  24.         }
  25.         max = Math.max(max,dp[i]);
  26.     }
  27.     return max;
  28. }

空间复杂度: O(n), 时间复杂度: O(n^2)

题解 – 耐心排序 – 思路

1. 把每个数字看做是一张扑克牌，从左到右按顺序处理每一个扑克牌
2. 将它压在(从左边数过来)第一个牌顶 ≥ 它的牌堆上面
3. 如果找不到牌顶 ≥ 它的牌堆, 就在最右边新建一个牌堆, 将它放入这个新牌堆中

4. 当处理完所有牌，最终牌堆的数量就是最长上升子序列的长度

为什么最终牌堆的数量就是最长上升子序列的长度?

根据摆放规则可以推出:
    第n个堆的堆顶元素A, 在第n-1个堆中, 一定存在一个元素B, 元素B大于A且在原始数组中 A 排在B的前面;   只有B大于A, 才导致摆放B时需要重新建堆, 并且, 如果在原始数组中 A 排在B的后面且B大于A, 那么A与B将放在一个堆中, 所以堆的数量就是最长上升子序列的长度

题解 – 耐心排序 – 实现

  1. /**
  2.  * 最长上升子序列 -- 耐心排序优化
  3.  * @param nums
  4.  * @return
  5.  */
  6. static int lis2(int[] nums){
  7.     if(nums == null || nums.length == 0) return 0;
  8.     //牌堆的数量
  9.     int len = 0;
  10.     //牌顶数组
  11.     int[] top = new int[nums.length];
  12.     for (int num : nums) {
  13.         int j = 0;
  14.         while(j < len){
  15.             if(top[j] >= num){
  16.                 top[j] = num;
  17.                 break;
  18.             }
  19.             //牌顶 < num
  20.             j++;
  21.         }
  22.         if(j == len){  //新建一个堆顶
  23.             len++;
  24.             top[j] = num;
  25.         }
  26.     }
  27.     return len;
  28. }

题解 – 耐心排序 – 二分搜索 – 思路

假设数组是 nums，也就是最初的牌数组:
   1. top[i] 是第 i 个牌堆的牌顶，len 是牌堆的数量，初始值为 0
   2. 遍历每一张牌 num
       (1) 利用二分搜索找出 num 最终要放入的牌堆位置 index
       (2) num 作为第 index 个牌堆的牌顶，top[index] = num
       (3) 如果 index 等于 len，相当于新建一个牌堆，牌堆数量 +1，也就是 len++

题解 – 耐心排序 – 二分搜索 – 实现

  1. /**
  2.  * 最长上升子序列 -- 耐心排序优化 --二分搜索优化
  3.  *  时间复杂度 O(nlogn)
  4.  * @param nums
  5.  * @return
  6.  */
  7. static int lis3(int[] nums){
  8.     if(nums == null || nums.length == 0) return 0;
  9.     //牌堆的数量
  10.     int len = 0;
  11.     //牌顶数组
  12.     int[] top = new int[nums.length];
  13.     for (int num : nums) {
  14.         int begin = 0;
  15.         int end = len;
  16.         while (begin < end) {
  17.             int mid = (begin + end) >> 1;
  18.             if (num <= top[mid]) {
  19.                 end = mid;
  20.             } else {
  21.                 begin = mid + 1;
  22.             }
  23.         }
  24.         // 覆盖牌顶
  25.         top[begin] = num;
  26.         // 检查是否要新建一个牌堆
  27.         if (begin == len) len++;
  28.     }
  29.     return len;
  30. }

空间复杂度: O(n), 时间复杂度: O(nlogn)

算法4 – 最长公共子序列 (LCS)

最长公共子序列 (Longest Common Subsequence，LCS)

LeetCode: leetcode_1143_最长公共子序列

问题

求两个序列的最长公共子序列长度
例: [1, 3, 5, 9, 10] 和 [1, 4, 9, 10] 的最长公共子序列是 [1, 9, 10]，长度为 3

ABCBDAB 和 BDCABA 的最长公共子序列长度是 4，可能是
   ABCBDAB 和 BDCABA > BDAB
   ABCBDAB 和 BDCABA > BDAB
   ABCBDAB 和 BDCABA > BCAB
   ABCBDAB 和 BDCABA > BCBA

思路

1. 假设 2 个序列分别是 nums1、nums2 (i ∈ [1, nums1.length],  j ∈ [1, nums2.length] )

2. 假设 dp(i, j) 是【nums1 前 i 个元素】与【nums2 前 j 个元素】的最长公共子序列长度
    a. dp(i, 0)、dp(0, j) 初始值均为 0
    b. 如果 nums1[i – 1] = nums2[ j – 1], 那么 dp(i, j) = dp(i – 1, j – 1) + 1
    c. 如果 nums1[i – 1] ≠ nums2[ j – 1], 那么 dp(i, j) = max { dp(i – 1, j), dp(i, j – 1) }

题解 – 递归实现

  1. /**
  2.  * 最长公共子序列 (递归)
  3.  */
  4. static int lcs(int[] nums1, int[] nums2){
  5.     if(nums1 == null || nums1.length == 0) return 0;
  6.     if(nums2 == null || nums2.length == 0) return 0;
  7.     return lcs(nums1,nums1.length,nums2,nums2.length);
  8. }
  9.  
  10. /**
  11.  * @param nums1 数组1
  12.  * @param i     数组1中前i个元素: [0,i-1]
  13.  * @param nums2 数组2
  14.  * @param j     数组2中前j个元素:[0,j-1]
  15.  * @return
  16.  */
  17. static int lcs(int[] nums1, int i, int[] nums2, int j){
  18.     if(i == 0 || j == 0) return 0;
  19.     if(nums1[i-1] != nums2[j-1]){
  20.         /**
  21.          * 此处递归的意义在于:
  22.          *   如果数组nums1的第i-1个元素与数组nums2的第j-1个元素不相等, 那么
  23.          *   1. 比对数组nums1的前i-1个元素与数组nums2的前j个元素, 存在的最长公共子序列
  24.          *   2. 比对数组nums1的前i个元素与数组nums2的前j-1个元素, 存在的最长公共子序列
  25.          * 在到达递归基后的逻辑可以理解为, 遍历数组nums1每个元素, 去比对数组nums2的每一个元素,如果存在相同的, 则公共子序列数量加一
  26.          */
  27.         return Math.max(
  28.                 lcs(nums1,i-1,nums2,j),
  29.                 lcs(nums1,i,nums2,j-1));
  30.     }
  31.     return lcs(nums1,i-1,nums2,j-1) + 1;
  32. }

空间复杂度: O(k), k = min{n, m}, n、m 是2个序列的长度
时间复杂度: O(2n), 当 n = m 时

递归实现分析

出现重复递归调用

题解 – 非递归实现

  1. /**
  2.  * 最长公共子序列 (非递归)
  3.  * @param nums1
  4.  * @param nums2
  5.  * @return
  6.  */
  7. static int lcs2(int[] nums1, int[] nums2){
  8.     if(nums1 == null || nums1.length == 0) return 0;
  9.     if(nums2 == null || nums2.length == 0) return 0;
  10.     int[][] dp = new int[nums1.length+1][nums2.length+1];
  11.     for (int i = 1; i <= nums1.length; i++) {
  12.         /**
  13.          * 遍历nums1中的每一个元素, 与nums2中进行比较
  14.          *   如果相同, 则更新dp[i][j]的值 (dp[i][j]表示nums1数组前i个元素与nums2数组前j个元素存在的最长公共子序列长度)
  15.          *   如果不同, 则比较 nums1数组前i个元素与nums2数组前j-1个元素存在的最长公共子序列长度
  16.          *                和  nums1数组前i-1个元素与nums2数组前j个元素存在的最长公共子序列长度
  17.          *            取较大的值
  18.          */
  19.         for (int j = 1; j <= nums2.length; j++) {
  20.             if(nums1[i-1] == nums2[j-1]){ //i与j的含义为数组的前i个元素,前j个元素, 不包含第i,j个元素
  21.                 dp[i][j] = dp[i-1][j-1] + 1;
  22.             }else{
  23.                 dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
  24.             }
  25.         }
  26.     }
  27.     return dp[nums1.length][nums2.length];
  28. }

空间复杂度: O(n ∗ m)
时间复杂度: O(n ∗ m)

dp 数组的计算结果如下所示:

 

题解 – 非递归实现 – 滚动数组优化

使用滚动数组优化空间复杂度

  1. /**
  2.  * 最长公共子序列 (非递归 -- 滚动数组优化)
  3.  * @param nums1
  4.  * @param nums2
  5.  * @return
  6.  */
  7. static int lcs3(int[] nums1, int[] nums2){
  8.     if(nums1 == null || nums1.length == 0) return 0;
  9.     if(nums2 == null || nums2.length == 0) return 0;
  10.     int[][] dp = new int[2][nums2.length+1];
  11.     for (int i = 1; i <= nums1.length; i++) {
  12.         /**
  13.          * 遍历nums1中的每一个元素, 与nums2中进行比较
  14.          *   如果相同, 则更新dp[i][j]的值 (dp[i][j]表示nums1数组前i个元素与nums2数组前j个元素存在的最长公共子序列长度)
  15.          *   如果不同, 则比较 nums1数组前i个元素与nums2数组前j-1个元素存在的最长公共子序列长度
  16.          *                和  nums1数组前i-1个元素与nums2数组前j个元素存在的最长公共子序列长度
  17.          *            取较大的值
  18.          */
  19.         int row = i & 1; // i % 2; ==取模优化==>>i & 1;
  20.         int prevRow = (i-1) & 1;// (i-1) % 2; ==取模优化==>>(i-1) & 1;
  21.         for (int j = 1; j <= nums2.length; j++) {
  22.             if(nums1[i - 1] == nums2[j-1]){ //i与j的含义为数组的前i个元素,前j个元素, 不包含第i,j个元素
  23.                 dp[row][j] = dp[prevRow][j-1] + 1;
  24.             }else{
  25.                 dp[row][j] = Math.max(dp[prevRow][j],dp[row][j-1]);
  26.             }
  27.         }
  28.     }
  29.     return dp[nums1.length & 1][nums2.length];
  30. }

题解 – 非递归实现 – 一维数组优化

  1. /**
  2.  * 最长公共子序列 (非递归 -- 一维数组)
  3.  * @param nums1
  4.  * @param nums2
  5.  * @return
  6.  */
  7. static int lcs4(int[] nums1, int[] nums2){
  8.     if(nums1 == null || nums1.length == 0) return 0;
  9.     if(nums2 == null || nums2.length == 0) return 0;
  10.     int[] dp = new int[nums2.length+1];
  11.     for (int i = 1; i <= nums1.length; i++) {
  12.         int cur = 0;
  13.         for (int j = 1; j <= nums2.length; j++) {
  14.             int leftTop = cur;
  15.             /**
  16.              * 此时dp[j]代表计算到上一行中第j个元素时,存在公共子序列, 将dp[j]暂存于cur中, 当计算下一个元素时需要使用
  17.              */
  18.             cur = dp[j];
  19.             if(nums1[i - 1] == nums2[j-1]){
  20.                 dp[j] = leftTop + 1;
  21.             }else{
  22.                 dp[j] = Math.max(dp[j],dp[j-1]);
  23.             }
  24.         }
  25.     }
  26.     return dp[nums2.length];
  27. }

题解 – 非递归实现 – 一维数组优化 –  空间复杂度优化

空间复杂度优化至 O k  , k = min{n, m}

  1. /**
  2.  * 最长公共子序列 (非递归 -- 一维数组, 空间复杂度优化)
  3.  * @param nums1
  4.  * @param nums2
  5.  * @return
  6.  */
  7. static int lcs5(int[] nums1, int[] nums2){
  8.     if(nums1 == null || nums1.length == 0) return 0;
  9.     if(nums2 == null || nums2.length == 0) return 0;
  10.     //优化dp数组的长度, 使用nums1和nums2中较小的长度来初始化dp数组
  11.     int[] colsNums = nums2;
  12.     int[] rowsNums = nums1;
  13.     if(nums1.length < nums2.length){
  14.         colsNums = nums1;
  15.         rowsNums = nums2;
  16.     }
  17.     int[] dp = new int[colsNums.length+1];
  18.     for (int i = 1; i <= rowsNums.length; i++) {
  19.         int cur = 0;
  20.         for (int j = 1; j <= colsNums.length; j++) {
  21.             int leftTop = cur;
  22.             /**
  23.              * 此时dp[j]代表计算到上一行中第j个元素时,存在公共子序列, 将dp[j]暂存于cur中, 当计算下一个元素时需要使用
  24.              */
  25.             cur = dp[j];
  26.             if(nums1[i - 1] == rowsNums[j-1]){
  27.                 dp[j] = leftTop + 1;
  28.             }else{
  29.                 dp[j] = Math.max(dp[j],dp[j-1]);
  30.             }
  31.         }
  32.     }
  33.     return dp[colsNums.length];
  34. }
  35.  
  36.

算法5 – 最长公共子串

最长公共子串 (Longest Common Substring), 子串是连续的子序列

问题

求两个字符串的最长公共子串长度, ABCBA 和 BABCA 的最长公共子串是 ABC，长度为 3

思路

1. 假设 2 个字符串分别是 str1、str2
      i ∈ [1, str1.length]
      j ∈ [1, str2.length]
2. 假设 dp(i, j) 是以 str1[i – 1]、str2[ j – 1] 结尾的最长公共子串长度
      dp(i, 0)、dp(0, j) 初始值均为 0
      如果 str1[i – 1] = str2[ j – 1]，那么 dp(i, j) = dp(i – 1, j – 1) + 1
      如果 str1[i – 1] ≠ str2[ j – 1]，那么 dp(i, j) = 0
3. 最长公共子串的长度是所有 dp(i, j) 中的最大值 max { dp(i, j) }

题解 – 实现

  1. static int lcs(String str1, String str2){
  2.     if(str1 == null || str2 == null) return 0;
  3.     char[] chars1 = str1.toCharArray();
  4.     if(chars1.length == 0) return 0;
  5.     char[] chars2 = str2.toCharArray();
  6.     if(chars2.length == 0) return 0;
  7.     int[][] dp = new int[chars1.length+1][chars2.length+1];
  8.     int max = 0;
  9.     for (int i = 1; i <= chars1.length; i++) {
  10.         for (int j = 1; j <= chars2.length; j++) {
  11.             /**
  12.              * 在计算chars1数组中前i个元素与chars2数组前j个元素时:
  13.              * 如果第i-1个元素与第j-1个元素相等, 那么公共子串的长度为chars1数组中前i-1个元素与chars2数组前j-1个元素的最长公共子串长度 + 1
  14.              */
  15.             if(chars1[i-1] == chars2[j-1]){
  16.                 dp[i][j] = dp[i-1][j-1] + 1;
  17.             }
  18.             max = Math.max(dp[i][j], max);
  19.         }
  20.     }
  21.     return max;
  22. }

空间复杂度: O(n ∗ m)
时间复杂度: O(n ∗ m)

dp 数组的计算结果如下所示

题解 – 一维数组优化

  1. /**
  2.  * 最长公共子串优化 -- 一维数组
  3.  * @param str1
  4.  * @param str2
  5.  * @return
  6.  */
  7. static int lcs2(String str1, String str2){
  8.     if(str1 == null || str2 == null) return 0;
  9.     char[] chars1 = str1.toCharArray();
  10.     if(chars1.length == 0) return 0;
  11.     char[] chars2 = str2.toCharArray();
  12.     if(chars2.length == 0) return 0;
  13.  
  14.     int[] dp = new int[chars2.length+1];
  15.     int max = 0;
  16.     for (int i = 1; i <= chars1.length; i++) {
  17.         int cur = 0;
  18.         for (int j = 1; j <= chars2.length; j++) {
  19.             int leftTop = cur;
  20.             cur = dp[j];
  21.             if(chars1[i-1] == chars2[j-1]){
  22.                 dp[j] = leftTop + 1;
  23.             }
  24.             max = Math.max(dp[j], max);
  25.         }
  26.     }
  27.     return max;
  28. }

空间复杂度: O(k), k = min{n, m}, 时间复杂度: O(n ∗ m)

题解 – 一维数组优化 – 空间复杂度优化

  1. /**
  2.  * 最长公共子串优化 -- 一维数组 -- 行列优化
  3.  * @param str1
  4.  * @param str2
  5.  * @return
  6.  */
  7. static int lcs3(String str1, String str2){
  8.     if(str1 == null || str2 == null) return 0;
  9.     char[] chars1 = str1.toCharArray();
  10.     if(chars1.length == 0) return 0;
  11.     char[] chars2 = str2.toCharArray();
  12.     if(chars2.length == 0) return 0;
  13.     char[] colsChars = chars2, rowsChars = chars1;
  14.     if(chars1.length < chars2.length){
  15.         colsChars = chars1;
  16.         rowsChars = chars2;
  17.     }
  18.     int[] dp = new int[colsChars.length+1];
  19.     int max = 0;
  20.     for (int i = 1; i <= rowsChars.length; i++) {
  21.         int cur = 0;
  22.         for (int j = 1; j <= colsChars.length; j++) {
  23.             int leftTop = cur;
  24.             cur = dp[j];
  25.             if(rowsChars[i-1] == colsChars[j-1]){
  26.                 dp[j] = leftTop + 1;
  27.             }
  28.             max = Math.max(dp[j], max);
  29.         }
  30.     }
  31.     return max;
  32. }

题解 – 一维数组优化 – 空间复杂度优化 – 逆序优化

  1. /**
  2.  * 最长公共子串优化 -- 一维数组 -- 行列优化 -- 逆序优化
  3.  * @param str1
  4.  * @param str2
  5.  * @return
  6.  */
  7. static int lcs4(String str1, String str2){
  8.     if(str1 == null || str2 == null) return 0;
  9.     char[] chars1 = str1.toCharArray();
  10.     if(chars1.length == 0) return 0;
  11.     char[] chars2 = str2.toCharArray();
  12.     if(chars2.length == 0) return 0;
  13.     char[] colsChars = chars2, rowsChars = chars1;
  14.     if(chars1.length < chars2.length){
  15.         colsChars = chars1;
  16.         rowsChars = chars2;
  17.     }
  18.     int[] dp = new int[colsChars.length+1];
  19.     int max = 0;
  20.     for (int row = 1; row <= rowsChars.length; row++) {
  21.         for (int col = colsChars.length; col >= 1 ; col--) {
  22.             if(rowsChars[row-1] == colsChars[col-1]){
  23.                 dp[col] = dp[col-1] + 1;
  24.             }
  25.             max = Math.max(dp[col], max);
  26.         }
  27.     }
  28.     return max;
  29. }

算法6 – 0-1背包

问题

1. 有 n 件物品和一个最大承重为 W 的背包，每件物品的重量是

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/716585
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。