[toc]

动态规划，简称DP

• 是求最优化问题的一种常用策略

◼ 通常的使用套路（一步一步优化）
① 暴力递归（自顶向下，出现了重叠子问题）

② 记忆化搜索（自顶向下）

③ 递推（自底向上）

1.动态规划的一些相关概念

① 将复杂的原问题拆解成若干个简单的子问题

② 每个子问题仅仅解决1次，并保存它们的解

③ 最后推导出原问题的解

◼ 可以用动态规划来解决的问题，通常具备2个特点

• 最优子结构（最优化原理）：通过求解子问题的最优解，可以获得原问题的最优解
• 无后效性
  ✓ 某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响（未来与过去无关）
  ✓ 在推导后面阶段的状态时，只关心前面阶段的具体状态值，不关心这个状态是怎么一步步推导出来的

1.1 无后效性

从起点（0, 0）走到终点（4, 4）一共有多少种走法？只能向右、向下走

image.png

假设 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) 的值是怎么求出来的

1.2 有后效性

还是上面的图
如果可以向左、向右、向上、向下走，并且同一个格子不能走 2 次
这个就是有后效性的
dp(i, j) 下一步要怎么走，还要关心上一步是怎么来的，
也就是还要关心 dp(i, j – 1)、dp(i – 1, j) 是怎么来的

2.动态规划的常规步骤

◼ 动态规划中的“动态”可以理解为是“会变化的状态”
① 定义状态（状态是原问题、子问题的解）
✓ 比如定义 dp(i) 的含义
② 设置初始状态（边界）
✓ 比如设置 dp(0) 的值
③ 确定状态转移方程
✓ 比如确定 dp(i) 和 dp(i – 1) 的关系

3.例子1 找零钱 leetcode 322

题目：leetcode_322_零钱兑换：https://leetcode-cn.com/problems/coin-change/

• 假设有25分、20分、5分、1分的硬币，现要找给客户41分的零钱，如何办到硬币个数最少？

3.1 思路

假设 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

3.2 代码

/**
     * 暴力递归（自顶向下的调用，出现了重叠子问题）
     *  // fib(40)
        

        // dp(41) = 凑够41需要的最少硬币数量 = min { dp(40), dp(36), dp(16), dp(21) } + 1
        // dp(41 - 1) = dp(40) = 凑够40需要的最少硬币数量
        // dp(41 - 5) = dp(36) = 凑够36需要的最少硬币数量
        // dp(41 - 25) = dp(16) = 凑够16需要的最少硬币数量
        // dp(41 - 20) = dp(21) = 凑够21需要的最少硬币数量
        // min { dp(40), dp(36), dp(16), dp(21) } + 1
     */
      int coins1(int n) {
        if (n < 1) return  double.maxFinite.toInt();
        if (n == 25 || n == 20 || n == 5 || n == 1) return 1;
        int min1 = min(coins1(n - 25), coins1(n - 20));
        int min2 = min(coins1(n - 5), coins1(n - 1));
        return min(min1, min2) + 1;
    }

优化递归，记忆搜索

///
  /// Author: liyanjun
  /// description: 记忆化搜索
  /// 自顶向下
  ///
  int coins2(int n) {
    if (n < 1) return -1;
    List<int> dp = List(n + 1);
    List<int> faces = [1, 5, 20, 25];
    for (var item in faces) {
      if (n < item) break;
      dp[item] = 1;
    }
    return coins2dp(n, dp);
  }

  int coins2dp(int n, List<int> dp) {
    if (n < 1) return  double.maxFinite.toInt();
    if (dp[n] == null) {
      int min1 = min(coins2dp(n - 25, dp), coins2dp(n - 20, dp));
      int min2 = min(coins2dp(n - 5, dp), coins2dp(n - 1, dp));
      dp[n] = min(min1, min2) + 1;
    }
    return dp[n];
  }

继续优化，不采用递归

  ///
  /// Author: liyanjun
  /// description: 递推（自底向上）
  ///
  int coins3(int n) {
    if (n < 1) {
      return -1;
    }
    List<int> dp = List(n + 1);
    dp[0] = 0;
   for (var i = 1; i <= n; i++) {
        int min1 = dp[i - 1];
            if (i >= 5) min1 = min(dp[i - 5], min1);
            if (i >= 20) min1 = min(dp[i - 20], min1);
            if (i >= 25) min1 = min(dp[i - 25], min1);
            dp[i] = min1 + 1;
   }
   return dp[n];
  }

如果打印内容

  ///
  /// Author: liyanjun
  /// description: 递推（自底向上）
  /// 输出选用了哪些
  ///
  int coins4(int n) {
    if (n < 1) {
      return -1;
    }
    List<int> dp = List(n + 1);
    dp[0] = 0;
    // faces[i]是凑够i分时最后那枚硬币的面值
    List<int> faces = List(n + 1);
    for (var i = 1; i <= n; i++) {
      int min1 = dp[i - 1];
      faces[i] = 1;
      if (i >= 5 && dp[i - 5] < min1) {
        min1 =dp[i - 5];
        faces[i] = 5;
      } //走到这里，如果选择dp[i - 5]，说明这次选的是5，否则是1
      if (i >= 20  && dp[i - 20] < min1) {
        min1 = dp[i - 20];
        faces[i] = 20;
      } //走到这里，如果选择dp[i - 20]，说明这次选的是20，否则是上面
      if (i >= 25  && dp[i - 25] < min1) {
        min1 =dp[i - 25];
        faces[i] = 25;
      } //走到这里，如果选择dp[i - 5]说明这次选的是25，否则是上面
      dp[i] = min1 + 1;
       print1(faces, i);
    }
    // print1(faces, n);
    return dp[n];
  }

  print1(List<int> faces, int n) {
    String res = '要找$n,需要的零钱是';
    while (n > 0) {
      res = '$res ${faces[n]}';
      n -= faces[n];
    }
    print(res);
  }

数组也是动态的

int coinChange(List<int> faces, int n) {
   if (n < 1 || faces == null || faces.length == 0) return -1;
    List<int> dp = List(n + 1);
    dp[0] = 0;
    for (var i = 1; i <= n; i++) {
      int min1 =   double.maxFinite.toInt();
            for ( int face in faces) {
                if (i < face) continue;
                min1 = min(dp[i-face], min1);
            }
       dp[i] = min1 + 1;
    }
    return  dp[n];
  }

4.例子2 最长连续子序列和

题目：leetcode_53_最大子序和：https://leetcode-cn.com/problems/maximum-subarray/

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

4.1 思路

状态定义：
假设 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)

4.2代码

  ///
  /// Author: liyanjun
  /// description: 动态规划
  /// 状态转移方程：
// * 如果 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)
  ///
  int maxSubArray3(List<int> nums) {
    if (nums == null || nums.length == 0) {
      return 0;
    }
    List<int> dp = List(nums.length);
    dp[0] = nums[0];
    int maxDp = dp[0];
    for (var i = 1; i < nums.length; i++) {
      if (dp[i-1] <=0) {
        dp[i] = nums[i];
      }else{
        dp[i] = dp[i-1] + nums[i];
      }
      maxDp = max(maxDp,  dp[i]);
    }
    return maxDp;
  } 

验证

 List<int> nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
  //  print(Solution().maxSubArray2(nums));
  print(Solution().maxSubArray3(nums));
  // 

结果

6

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

5. 例子3 最长上升子序列（LIS）

5.1 思路

假设数组是 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)

• 当 nums[i] > nums[j]
  • ✓ nums[i] 可以接在 nums[j] 后面，形成一个比 dp(j) 更长的上升子序列，长度为 dp(j) + 1
  • ✓ dp(i) = max { dp(i), dp(j) + 1 }
• 当 nums[i] <= nums[j]
  • nums[i] 不能接在 nums[j] 后面，跳过此次遍历（continue）

状态的初始值
dp(0) = 1

• 所有的 dp(i) 默认都初始化为 1

5.2 代码

int lengthOfLIS(List<int> nums) {
    if (nums == null || nums.length == 0) return 0;
    if (nums.length == 1) return 1;
    List<int> dp = List(nums.length);
    dp[0] = 1;
    int maxDp = dp[0];
     print('dp[0] ==${dp[0]}= nums[0]== ${nums[0]}');
    for (var i = 1; i < nums.length; i++) {
      dp[i] = 1;
        for (var j =0; j<i; j++) {
          if (nums[i] <= nums[j])  continue;
            dp[i] = max(dp[j] + 1,dp[i]); 
        }
      print('dp[$i] ==${dp[i]}= nums[$i]== ${nums[i]}');
      maxDp = max(maxDp, dp[i]);
    }
    return maxDp;
  }

   

空间复杂度：O(n)，时间复杂度：

5.3 二分法

5.3.1 思路

image.png

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

image.png

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

上面的逻辑代码实现

 ///
     /// Author: liyanjun
     /// description:扑克牌实现
     ///
   int lengthOfLIS1(List<int> nums) {
    if (nums == null || nums.length == 0) return 0;
    if (nums.length == 1) return 1;
    int len = 0;//牌堆的数量
    List<int> top = List.generate(nums.length, (_)=>0);//牌顶数组
    // 遍历所有的牌
        for (int num in nums) {
      int i = 0;
            while (i < len) {
        if (top[i]>=num) {//第一个牌顶 ≥ 它的牌堆上面
          top[i] = num;
          break;
        }
        i++;//牌顶<num
      }
      if (i==len) {//遍历所有牌堆 还是没有     则牌堆加1
         len ++;
         top[i] = num;//排定赋值
      }
      
        }
    return len;
  }

5.3.2 二分思路

因为牌堆是升序的，可以用二分优化
（假设数组是 nums，也就是最初的牌数组）

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

代码

///
  /// Author: liyanjun
  /// description:二分搜索
  ///
  int lengthOfLIS2(List<int> nums) {
    if (nums == null || nums.length == 0) return 0;
    if (nums.length == 1) return 1;
    int len = 0; //牌堆的数量
    List<int> top = List.generate(nums.length, (_) => 0); //牌顶数组
    // 遍历所有的牌
    //牌堆是有序的
    for (int num in nums) {
      int begin = 0;
      int end = len;
      while (begin < end) {
        int mid = (begin + end) >> 1;
        if (top[mid] >= num) {
          end = mid;
        }else{
           begin = mid + 1;
        }
      }
      // begin是最终要插入的位置
       top[begin] = num;
      if (begin == len) {
        len++;
      }
    }
    return len;
  }
}

6. 例子3 最长公共子序列（LCS）

题目：leetcode_1143_最长公共子序列：https://leetcode-cn.com/problems/longest-common-subsequence/

• [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

6.1 思路

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

假设 dp(i, j) 是【nums1 前 i 个元素】与【nums2 前 j 个元素】的最长公共子序列长度

• dp(i, 0)、dp(0, j) 初始值均为 0
• 如果 nums1[i – 1] = nums2[j – 1]，那么 dp(i, j) = dp(i – 1, j – 1) + 1
• 如果 nums1[i – 1] ≠ nums2[j – 1]，那么 dp(i, j) = max { dp(i – 1, j), dp(i, j – 1) }

6.2 递归实现代码

///
/// Author: liyanjun
/// description: 递归实现
///  
int longestCommonSubsequence1(String text1, String text2) {
   if (text1 == null || text2 == null || text1.length == 0 || text2.length == 0) return 0;
    List<String> nums1 = text1.split('');
    List<String> nums2 = text2.split('');
return lcs(nums1, nums1.length, nums2, nums2.length);
}

///
/// Author: liyanjun
/// description: 求nums1前i个元素和nums2前j个元素的最长公共子序列长度
///
int lcs(List<String>nums1,int i,List<String>nums2,int j){
  if (i == 0 || j == 0) return 0;
  if (nums1[i-1] == nums2[j-1]) {
    return lcs(nums1, i-1, nums2, j-1) + 1;
  }else{
    return max(lcs(nums1, i, nums2, j-1), lcs(nums1, i-1, nums2, j));
  }
}

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

6.3 动态规划代码

 if (text1 == null || text2 == null || text1.length == 0 || text2.length == 0) return 0;
    int len1 = text1.length;
    int len2 = text2.length;
    List<String> nums1 = text1.split('');
    List<String> nums2 = text2.split('');
    List<List<int>> dp = List.generate(len1+1, (_) => List.generate(len2+1, (_) => 0));
    //假设 dp(i, j) 是【nums1 前 i 个元素】与【nums2 前 j 个元素】的最长公共子序列长度

    for (int i = 1; i <=len1; i++) {
      for (int j = 1; j <= len2; j++) {
        if (nums1[i-1]==nums2[j-1]) {
          dp[i][j] = dp[i-1][j-1] +1;
        }else{
          dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
        }
        // print('dp[$i][$j] === ${dp[i][j]}');
      }
    }
    return dp[len1][len2];
  }

验证

 Solution s = Solution();
  String text1 = 'abcde';
  String text2 = 'abe';
  print(s.longestCommonSubsequence(text1, text2));
}

结果

3

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

6.3.1 动态规划优化1

image.png

每次求解都是利用上一行的数据求解当前行的数据，所以空间可以优化
利用滚动数组求解

  ///
/// Author: liyanjun
/// description: 动态规划实现
///滚动数组，只需要用两行即可

  int longestCommonSubsequence3(String text1, String text2) {
    if (text1 == null || text2 == null || text1.length == 0 || text2.length == 0) return 0;
    int len1 = text1.length;
    int len2 = text2.length;
    List<String> nums1 = text1.split('');
    List<String> nums2 = text2.split('');
    List<List<int>> dp = List.generate(2, (_) => List.generate(len2+1, (_) => 0));
    //假设 dp(i, j) 是【nums1 前 i 个元素】与【nums2 前 j 个元素】的最长公共子序列长度
    for (int i = 1; i <=len1; i++) {
      int row = i & 1;
            int prevRow = (i - 1) & 1;
      for (int j = 1; j <= len2; j++) {
        if (nums1[i-1]==nums2[j-1]) {
          dp[row][j] = dp[prevRow][j-1] +1;
        }else{
          dp[row][j] = max(dp[row][j-1], dp[prevRow][j]);
        }
      }
    }
    return dp[len1&1][len2];
  }
}

6.3.2 动态规划优化2

只需要一行即可，记住一行
可以将 二维数组 优化成 一维数组，进一步降低空间复杂度

 ///
/// Author: liyanjun
/// description: 动态规划实现
///从滚动数组优化
///只需要一行即可，记住一行，下一行覆盖上一行
///可以将 二维数组 优化成 一维数组，进一步降低空间复杂度

  int longestCommonSubsequence4(String text1, String text2) {
    if (text1 == null || text2 == null || text1.length == 0 || text2.length == 0) return 0;
    int len1 = text1.length;
    int len2 = text2.length;
    List<String> nums1 = text1.split('');
    List<String> nums2 = text2.split('');
    List<int> dp =  List.generate(len2+1, (_) => 0);
    //假设 dp(i, j) 是【nums1 前 i 个元素】与【nums2 前 j 个元素】的最长公共子序列长度
    for (int i = 1; i <=len1; i++) {
      int cur = 0;
      for (int j = 1; j <= len2; j++) {
        int leftTop = cur;
                cur = dp[j];
        if (nums1[i-1]==nums2[j-1]) {
          dp[j] = leftTop + 1;
          // dp[row][j] = dp[prevRow][j-1] +1;
        }else{
          dp [j] = max(dp[j-1], dp[j]);
          // dp[row][j] = max(dp[row][j-1], dp[prevRow][j]);
        }
      }
    }
    return dp[len2];
    // return dp[len1&1][len2];
  }
}

6.3.2 动态规划优化3

继续优化，选择较小的那个为列，作为一位数组

 ///
/// Author: liyanjun
/// description: 动态规划实现
///从滚动数组优化
///只需要一行即可，记住一行，下一行覆盖上一行
///可以将 二维数组 优化成 一维数组，进一步降低空间复杂度
///继续优化，选择较小的那个为lie，作为一位数组
  int longestCommonSubsequence5(String text1, String text2) {
    if (text1 == null || text2 == null || text1.length == 0 || text2.length == 0) return 0;
   
    List<String> nums1 = text1.split('');
    List<String> nums2 = text2.split('');
    List<String> row = nums1;
    List<String> col  = nums2;
    if (nums1.length<nums2.length) {
      row = nums2;
      col =  nums1;
    }
    List<int> dp =  List.generate(col.length+1, (_) => 0);
    //假设 dp(i, j) 是【nums1 前 i 个元素】与【nums2 前 j 个元素】的最长公共子序列长度
    for (int i = 1; i <=row.length; i++) {
      int cur = 0;//为了记录leftTop
      for (int j = 1; j <= col.length; j++) {
        int leftTop = cur;
                cur = dp[j];
        if (row[i-1]==col[j-1]) {
          dp[j] = leftTop + 1;
          // dp[row][j] = dp[prevRow][j-1] +1;
        }else{
          dp [j] = max(dp[j-1], dp[j]);
          // dp[row][j] = max(dp[row][j-1], dp[prevRow][j]);
        }
      }
    }
    return dp[col.length];
    // return dp[len1&1][len2];
  }

翻译成java，在leetcode结果对比，内存消耗在不断减少

image.png

7. 例子4 最长公共子串（LCS）

最长公共子串（Longest Common Substring）
子串是连续的子序列
求两个字符串的最长公共子串长度
ABCBA 和 BABCA 的最长公共子串是 ABC，长度为 3

7.1 思路

假设 2 个字符串分别是 str1、str2
i ∈ [1, str1.length]
j ∈ [1, str2.length]

◼ 假设 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

最长公共子串的长度是所有 dp(i, j) 中的最大值 max { dp(i, j) }

7.2代码

int longestCommonSubString(String text1, String text2) {
     if (text1 == null || text2 == null || text1.length == 0 || text2.length == 0) return 0;
    int len1 = text1.length;
    int len2 = text2.length;
    List<String> nums1 = text1.split('');
    List<String> nums2 = text2.split('');
    List<List<int>> dp = List.generate(len1+1, (_) => List.generate(len2+1, (_) => 0));
    //dp(i, j) 是以 str1[i – 1]、str2[j – 1] 结尾的最长公共子串长度
    int maxDp = 0;
    for (int i = 1; i <=len1; i++) {
      for (int j = 1; j <= len2; j++) {
        if (nums1[i-1] !=nums2[j-1]) continue;
          dp[i][j] = dp[i-1][j-1] +1;
          maxDp = max(maxDp,  dp[i][j]);
        // print('dp[$i][$j] === ${dp[i][j]}');
      }
    }
    return maxDp;
  }

7.3 代码优化1

跟6类似可以用两行

  ///
/// Author: liyanjun
/// description: 动态规划实现
///滚动数组，只需要去两行即可

  int longestCommonSubString1(String text1, String text2) {
    if (text1 == null || text2 == null || text1.length == 0 || text2.length == 0) return 0;
    int len1 = text1.length;
    int len2 = text2.length;
    List<String> nums1 = text1.split('');
    List<String> nums2 = text2.split('');
    List<List<int>> dp = List.generate(2, (_) => List.generate(len2+1, (_) => 0));
   //dp(i, j) 是以 str1[i – 1]、str2[j – 1] 结尾的最长公共子串长度
      int maxDp = 0;
    for (int i = 1; i <=len1; i++) {
      int row = i & 1;
            int prevRow = (i - 1) & 1;
      for (int j = 1; j <= len2; j++) {
        if (nums1[i-1] !=nums2[j-1])  continue;
          dp[row][j] = dp[prevRow][j-1] +1;
         maxDp = max(maxDp,  dp[row][j]);
        // print('dp[$i][$j] === ${dp[i][j]}');
      }
    }
    return maxDp;
  }

7.4 代码优化2

可以将 二维数组 优化成 一维数组，进一步降低空间复杂度

  int longestCommonSubsequence2(String text1, String text2) {
    if (text1 == null || text2 == null || text1.length == 0 || text2.length == 0) return 0;
    int len1 = text1.length;
    int len2 = text2.length;
    List<String> nums1 = text1.split('');
    List<String> nums2 = text2.split('');
    List<int> dp =  List.generate(len2+1, (_) => 0);
    //dp(i, j) 是以 str1[i – 1]、str2[j – 1] 结尾的最长公共子串长度
       int maxDp = 0;
    for (int i = 1; i <=len1; i++) {
      int cur = 0;//为了记录leftTop
      for (int j = 1; j <= len2; j++) {
        int leftTop = cur;
                cur = dp[j];
        if (nums1[i-1]!=nums2[j-1]) continue;
          dp[j] = leftTop + 1;
          // dp[row][j] = dp[prevRow][j-1] +1;
         maxDp = max(maxDp,  dp[j]);
      }
    }
    return maxDp;
  }

7.5 代码优化3

选择长度较小的为列，进一步优化空间

   ///
/// Author: liyanjun
/// description: 动态规划实现
///从滚动数组优化
///只需要一行即可，记住一行，下一行覆盖上一行
///可以将 二维数组 优化成 一维数组，进一步降低空间复杂度
///继续优化，选择较小的那个为lie，作为一位数组
  int longestCommonSubsequence3(String text1, String text2) {
    if (text1 == null || text2 == null || text1.length == 0 || text2.length == 0) return 0;
   
    List<String> nums1 = text1.split('');
    List<String> nums2 = text2.split('');
    List<String> row = nums1;
    List<String> col  = nums2;
    if (nums1.length<nums2.length) {
      row = nums2;
      col =  nums1;
    }
    List<int> dp =  List.generate(col.length+1, (_) => 0);
    //dp(i, j) 是以 str1[i – 1]、str2[j – 1] 结尾的最长公共子串长度
       int maxDp = 0;
    for (int i = 1; i <=row.length; i++) {
      int cur = 0;//为了记录leftTop
      for (int j = 1; j <= col.length; j++) {
        int leftTop = cur;
                cur = dp[j];
        if (row[i-1]==col[j-1]){
          dp[j] = leftTop + 1;
          }else{
           dp[j] = 0;
          }
          // dp[row][j] = dp[prevRow][j-1] +1;
       maxDp = max(maxDp,  dp[j]);
      }
    }
    return maxDp;
  }
}

8 列子5 0-1背包问题

有 n 件物品和一个最大承重为 W 的背包，每件物品的重量是 𝑤i、价值是 𝑣i

• 在保证总重量不超过 W 的前提下，选择某些物品装入背包，背包的最大总价值是多少？
• 注意：每个物品只有 1 件，也就是每个物品只能选择 0 件或者 1 件

8.1 思路

假设 values 是价值数组，weights 是重量数组
编号为 k 的物品，价值是 values[k]，重量是 weights[k]，k ∈ [0, n)

定义状态
假设 dp(i, j) 是 最大承重为 j、有前 i 件物品可选 时的最大总价值，i ∈ [1, n]，j ∈ [1, W]

• dp(i, 0)、dp(0, j) 初始值均为 0
• 如果 j < weights[i – 1]，那么 dp(i, j) = dp(i – 1, j)
• 如果 j ≥ weights[i – 1]，那么 dp(i, j) = max { dp(i – 1, j), dp(i – 1, j – weights[i – 1]) + values[i – 1] }
• 若果j<weights[i-1],则dp(i,j)=dp(i-1,j);
• 否则也有两个情况
  • 如果不选择第i个物品，则dp(i,j)=dp(i-1,j);
  • 如果选择第i个物品，则dp(i,j) = values[i-1] + dp(i-1,j-weights[i-1])

8.2 代码

int selectMax(List<int> values, List<int> weights, int capacity) {
    if (values == null ||
        values.length == 0 ||
        weights == null ||
        weights.length == 0 ||
        weights.length != values.length||
        capacity <= 0) return 0;
    // 假设 dp(i, j) 是 最大承重为 j、有前 i 件物品可选 时的最大总价值，i ∈ [1, n]，j ∈ [1, W]
    List<List<int>> dp =
        List.generate(values.length + 1, (_) => List.generate(capacity + 1, (_) => 0));
    for (int i = 1; i <= values.length; i++) {
      for (int j = 1; j <= capacity; j++) {
        if (j < weights[i - 1]) {
          dp[i][j] = dp[i - 1][j];
        } else {
          dp[i][j] = max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]]);
        }
      }
    }
    return dp[values.length][capacity];
  }

8.3 优化

可以优化为1维数组
例子如

 List<int> values = [6, 3, 5, 4, 6];
 List<int> weights = [2, 2, 6, 5, 4];
 int capacity = 10;

dp数组如下

image.png

• dp(i, j) 都是由 dp(i – 1, k) 推导出来的，也就是说，第 i 行的数据是由它的上一行第 i – 1 行推导出来的
• 因此，可以使用一维数组来优化

只用到上一行的数据，另外，由于 k ≤ j ，所以 j 的遍历应该由大到小，否则导致数据错乱,即dp[i - 1][j - weights[i - 1]的数据不好获取，可以从右到左开始
所以代码可以优化为，

   int selectMax1(List<int> values, List<int> weights, int capacity) {
    if (values == null ||
        values.length == 0 ||
        weights == null ||
        weights.length == 0 ||
        weights.length != values.length||
        capacity <= 0) return 0;
    // 假设 dp(i, j) 是 最大承重为 j、有前 i 件物品可选 时的最大总价值，i ∈ [1, n]，j ∈ [1, W]
    //优化为1维数组，
  List<int> dp =
       List.generate(capacity + 1, (_) => 0);
    for (int i = 1; i <= values.length; i++) {
      for (int j = capacity; j >=1; j--) {
        if (j < weights[i - 1]) continue;
          dp[j] = max(dp[j], values[i - 1] + dp[j - weights[i - 1]]);
      }
    }
    return dp[capacity];
  }
}

8.4 优化1

观察二维数组表，得出结论：j 的下界可以从 1 改为 weights[i – 1]

 int selectMax1(List<int> values, List<int> weights, int capacity) {
    if (values == null ||
        values.length == 0 ||
        weights == null ||
        weights.length == 0 ||
        weights.length != values.length||
        capacity <= 0) return 0;
    // 假设 dp(i, j) 是 最大承重为 j、有前 i 件物品可选 时的最大总价值，i ∈ [1, n]，j ∈ [1, W]
    //优化为1维数组，◼ dp(i, j) 都是由 dp(i – 1, k) 推导出来的，也就是说，第 i 行的数据是由它的上一行第 i – 1 行推导出来的
// 因此，可以使用一维数组来优化
// ◼ 观察二维数组表，得出结论：j 的下界可以从 1 改为 weights[i – 1]

  List<int> dp =
       List.generate(capacity + 1, (_) => 0);
    for (int i = 1; i <= values.length; i++) {
      for (int j = capacity; j >=weights[i-1]; j--) {
        if (j < weights[i - 1]) continue;
          dp[j] = max(dp[j], values[i - 1] + dp[j - weights[i - 1]]);
      }
    }
    return dp[capacity];
  }
}

9 列子6 背包问题变化1-恰好装满

有 n 件物品和一个最大承重为 W 的背包，每件物品的重量是 𝑤i、价值是 𝑣i

• 在保证总重量恰好等于 W 的前提下，选择某些物品装入背包，背包的最大总价值是多少？
• 注意：每个物品只有 1 件，也就是每个物品只能选择 0 件或者 1 件

9.1 思路

只需要在8的基础上
dp(i, j) 初始状态调整

• dp(i, 0) = 0，总重量恰好为 0，最大总价值必然也为 0
• dp(0, j) = –∞（负数），j ≥ 1，负数在这里代表无法恰好装满

9.2 代码

 ///
  /// Author: liyanjun
  /// description: 恰好装满
  ///返回-1，没法刚好凑好容量
  int selectMaxExactly1(List<int> values, List<int> weights, int capacity) {
    if (values == null ||
        values.length == 0 ||
        weights == null ||
        weights.length == 0 ||
        weights.length != values.length||
        capacity <= 0) return 0;
    // 假设 dp(i, j) 是 最大承重为 j、有前 i 件物品可选 时的最大总价值，i ∈ [1, n]，j ∈ [1, W]
    //优化为1维数组，◼ dp(i, j) 都是由 dp(i – 1, k) 推导出来的，也就是说，第 i 行的数据是由它的上一行第 i – 1 行推导出来的
// 因此，可以使用一维数组来优化
// ◼ 观察二维数组表，得出结论：j 的下界可以从 1 改为 weights[i – 1]

  List<int> dp =
       List.generate(capacity + 1, (i) =>i==0?0:double.maxFinite.toInt()*-1);
      
    for (int i = 1; i <= values.length; i++) {
      for (int j = capacity; j >=weights[i-1]; j--) {
          dp[j] = max(dp[j], values[i - 1] + dp[j - weights[i - 1]]);
          // print('dp[$j] ===${dp[j]}');
      }
    }
    return dp[capacity]<0?-1:dp[capacity];
  }

}