黑马程序员技术交流社区

标题: 【上海校区】动态规划基础 [打印本页]

作者: 梦缠绕的时候 时间: 2019-1-9 09:33
标题: 【上海校区】动态规划基础
本帖最后由梦缠绕的时候于 2019-1-9 09:35 编辑

什么是动态规划？
通过使用递归、记忆化搜索、动态规划三种方法解斐波那契数列问题，来说明
递归
从上而下
但存在大量重复计算
举例： f(10)=f(9)+f(8) 与 f(9)=f(8)+f(7) 这里f(8)就被重复计算了
#include <iostream>
#include <ctime>

using namespace std;

int num = 0;

// 递归求斐波那契数列
int fib( int n ){

num ++;

if( n == 0 )
      return 0;

if( n == 1 )
      return 1;

return fib(n-1) + fib(n-2);
}

记忆化搜索
在递归的基础上优化
将计算过的f(n)都保存起来, 避免重复计算
#include <iostream>
#include <ctime>
#include <vector>

using namespace std;

vector<int> memo;  // 用来保存计算过的数值
int num = 0;

// 记忆化搜索
int fib(int n){

num ++;

if(n == 0)
      return 0;

if(n == 1)
      return 1;

if(memo[n] == -1)
      memo[n] = fib(n - 1) + fib(n - 2);

return memo[n];
}
动态规划
递归是从上而下的，动态规划则是自下而上的
#include <iostream>
#include <ctime>
#include <vector>
using namespace std;

// 动态规划
int fib( int n ){

vector<int> memo(n + 1, -1);

memo[0] = 0;
memo[1] = 1;
for(int i = 2 ; i <= n ; i ++)
      memo = memo[i - 1] + memo[i - 2];

return memo[n];
}

一般来说，记忆化搜索也属于动态规划范畴
二.第一个动态规划问题 Climbing Stairs
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释：有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶
示例 2：

输入： 3
输出： 3
解释：有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶
递归解决
直接使用依然会存在重复计算的问题
配合记忆化搜索来解决问题
#include <iostream>
#include <vector>

using namespace std;

/// 70. Climbing Stairs
///
/// 记忆化搜索
/// 时间复杂度: O(n)
/// 空间复杂度: O(n)
class Solution {

private:
vector<int> memo;  // 存储计算过的内容

int calcWays(int n){

      if(n == 0 || n == 1)
         return 1;

      if(memo[n] == -1)  // memo[n] 如果没有计算过
         memo[n] = calcWays(n - 1) + calcWays(n - 2);

      return memo[n];
}
动态规划
自下而上的解决问题
#include <iostream>
#include <vector>

using namespace std;

/// 70. Climbing Stairs
///
/// 动态规划
/// 时间复杂度: O(n)
/// 空间复杂度: O(n)
class Solution {

public:
int climbStairs(int n) {

      vector<int> memo(n + 1, -1);
      memo[0] = 1;
      memo[1] = 1;
      for(int i = 2 ; i <= n ; i ++)
         memo = memo[i - 1] + memo[i - 2];
      return memo[n];
}
};
三. 发现重叠子问题 Integer Break
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
解题思路
重叠子问题：在寻找子问题的最大乘积中得到答案
以4为例：寻找3, 2, 1的最大乘积
代码
暴力解法: 回溯法
#include <iostream>
#include <cassert>

using namespace std;

/// 343. Integer Break
///
/// 暴力搜索
/// 在Leetcode中提交这个版本的代码会超时! (Time Limit Exceeded)
/// 时间复杂度: O(n^n)
/// 空间复杂度: O(n)
class Solution {

private:
int max3(int a, int b, int c){
      return max(a, max(b, c));
}

// 将n进行分割(至少分割两部分), 可以获得的最大乘积
int breakInteger(int n){

      if(n == 1)
         return 1;

      int res = -1;
      for(int i = 1 ; i <= n - 1 ; i ++)
         res = max3(res, i * (n - i), i * breakInteger(n - i));
         // n-i  与n-i的分割的最大乘积, 需要比较
      return res;
}

public:
int integerBreak(int n) {
      assert(n >= 1);
      return breakInteger(n);
}
};
记忆化搜索
#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// 343. Integer Break
///
/// 记忆化搜索
/// 时间复杂度: O(n^2)
/// 空间复杂度: O(n)
class Solution {
private:
vector<int> memo;

int max3(int a, int b, int c){
      return max(a, max(b, c));
}

// 将n进行分割(至少分割两部分), 可以获得的最大乘积
int breakInteger(int n){

      if(n == 1)
         return 1;

      if(memo[n] != -1)
         return memo[n];

      int res = -1;
      for(int i = 1 ; i <= n - 1 ; i ++)
         res = max3(res, i * (n - i) , i * breakInteger(n - i));
      memo[n] = res;
      return res;
}

public:
int integerBreak(int n) {
      assert(n >= 1);
      memo.clear();
      for(int i = 0 ; i < n + 1 ; i ++)
         memo.push_back(-1);
      return breakInteger(n);
}
};
动态规划
#include <iostream>
#include <vector>

using namespace std;

/// 343. Integer Break
///
/// 动态规划
/// 时间复杂度: O(n^2)
/// 空间复杂度: O(n)
class Solution {

private:
int max3(int a, int b, int c ){
      return max(max(a, b), c);
}

public:
int integerBreak(int n) {

      assert(n >= 1);

      // memo 表示将数字i分割(至少分割成两部分)后得到的最大乘积
      vector<int> memo(n + 1, -1);

      memo[1] = 1;
      for(int i = 2 ; i <= n ; i ++)
         // 求解memo
         for(int j = 1 ; j <= i - 1 ; j ++)
            memo = max3(memo, j * (i - j), j * memo[i - j]);
            // i-j 一定<i 所以memo[i-j]此时已经被计算出来了

      return memo[n];
}
};
四. 状态的定义和状态转移 House Robber
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
   偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
   偷窃到的最高金额 = 2 + 9 + 1 = 12
解题思路
重叠子问题: 根据第一个偷取的选择, 从偷取0 偷取1....偷取n-1 ，n个子问题
注意点
注意其中对状态的定义:
考虑偷取  [x..n-1] 范围里的房子, 这里x并不是一定要偷取的

这样可以写出偷取[0..n-1]范围的房子的最大获取价值函数(状态转移方程):
f(0) = max{V(0) + f(0+2), V(1) + f(1+2), V(2) + f(2+2), ..., v(n-3) + f(n-1), V(n-2), V(n-1)}

这里 '状态转移' 与 '状态转移方程' 是比较重要的概念
记忆化搜索代码
#include <iostream>
#include <vector>

using namespace std;

/// 198. House Robber
///
/// 记忆化搜索
/// 时间复杂度: O(n^2)
/// 空间复杂度: O(n)
class Solution {

private:
// memo 表示考虑抢劫 nums[i...n) 所能获得的最大收益
vector<int> memo;

// 考虑抢劫nums[index...nums.size())这个范围的所有房子
int tryRob(const vector<int> &nums, int index){

      if(index >= nums.size())
         return 0;

      if(memo[index] != -1)
         return memo[index];

      int res = 0;
      for(int i = index ; i < nums.size() ; i ++)
         res = max(res, nums + tryRob(nums, i + 2));
      memo[index] = res;
      return res;
}

public:
int rob(vector<int>& nums) {

      memo.clear();
      for(int i = 0 ; i < nums.size() ; i ++)
         memo.push_back(-1);  // 记忆化搜索  空间中的值初始化为 -1
      return tryRob(nums, 0);
}
};
动态规划代码
从最后一种状态: 取n-1 的情况, 一次往前递推
#include <iostream>
#include <vector>

using namespace std;

/// 198. House Robber
///
/// 动态规划
/// 时间复杂度: O(n^2)
/// 空间复杂度: O(n)
class Solution {

public:
int rob(vector<int>& nums) {

      int n = nums.size();

      if(n == 0)
         return 0;

      // memo 表示考虑抢劫 nums[i...n) 所能获得的最大收益
      vector<int> memo(n, 0);
      memo[n - 1] = nums[n - 1];  // n-1的状态的最大收益, 是最明显的，更此向前递推
      for(int i = n - 2 ; i >= 0 ; i --)
         for (int j = i; j < n; j++)
            memo = max(memo,
                           nums[j] + (j + 2 < n ? memo[j + 2] : 0));

      return memo[0];
}
};
五. 0-1 背包问题
有一个背包，它的容量为C(Capacity)。现在有n种不同的物品，编号为0...n-1，
其中每一件物品的重量为w(i), 价值为v(i)。

问可以向这个背包中盛放哪些物品，使得在不超过背包容量的基础上，物品的总价值最大？
解题思路
F(n,c) 考虑将n个物品放进容量为C的背包，使得价值最大

F(i,c) 有两种情况：
   1. 第i个物品不放进背包    F(i,c) = F(i-1, c)
   2. 第i个物品放进背包    F(i,c) = v(i) + F(i-1, c - w(i))


所以该问题的状态转移方程为:
   F(i,c) = max(F(i-1,c), v(i)+F(i-1, c-w(i)))
代码
记忆化搜索
#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// 背包问题
/// 记忆化搜索
/// 时间复杂度: O(n * C) 其中n为物品个数; C为背包容积
/// 空间复杂度: O(n * C)
class Knapsack01{

private:
vector<vector<int>> memo;  // 记忆化搜索  的存储空间，这里是二维的分别是：  第几个物品  背包剩余容量

// 用 [0...index]的物品,填充容积为c的背包的最大价值
int bestValue(const vector<int> &w, const vector<int> &v, int index, int c){

      if(c <= 0 || index < 0)
         return 0;

      if(memo[index][c] != -1)
         return memo[index][c];

      int res = bestValue(w, v, index-1, c);  //第index个物品直接不要
      if(c >= w[index])
         res = max(res, v[index] + bestValue(w, v, index - 1, c - w[index]));
      memo[index][c] = res;
      return res;
}

public:
int knapsack01(const vector<int> &w, const vector<int> &v, int C){
      assert(w.size() == v.size() && C >= 0);
      int n = w.size();
      if(n == 0 || C == 0)
         return 0;

      memo.clear();
      for(int i = 0 ; i < n ; i ++)
         memo.push_back(vector<int>(C + 1, -1));
      return bestValue(w, v, n - 1, C);
}
};

int main() {

int n, W;
cin >> n >> W;

int v, w;
vector<int> vs, ws;
for(int i = 0 ; i < n ; i ++){
      cin >> w >> v;
      vs.push_back(v);
      ws.push_back(w);
}

cout << Knapsack01().knapsack01(ws, vs, W) << endl;

return 0;
}
动态规划(二维数组中去实现)
以一个简单化的背包问题为例：

有三个物品如下：
id       0 1 2
weight    1 2 3
value    6 10 12

现在有一个容量为5的背包

实现过程如下(横坐标为容量, 纵坐标为物品id)：

0 1 2 3 4 5
0 0 6 6 6 6 6
1 0 6 10  16  16  16
2 0 6 10  16  18  22

以(4,2)=18  为例，思考过程如下:
放入id为2的物品，容量剩余1，  横坐标为1的列中最大值(前一行对应容量的地方即之前的最大值)为6
所以在放入物品2 的前提下， value最大为 12+6=18  比之前的16要大，所以(4,2)=18,
如果比(4,1)小的话，值依然取(4,1)
代码

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// 背包问题
/// 动态规划
/// 时间复杂度: O(n * C) 其中n为物品个数; C为背包容积
/// 空间复杂度: O(n * C)
class Knapsack01{

public:
int knapsack01(const vector<int> &w, const vector<int> &v, int C){
      assert(w.size() == v.size() && C >= 0);
      int n = w.size();
      if(n == 0 || C == 0)
         return 0;

      vector<vector<int>> memo(n, vector<int>(C + 1,0));

      for(int j = 0 ; j <= C ; j ++) // j表示容量
         memo[0][j] = (j >= w[0] ? v[0] : 0 );  // id为0的物品先考虑

      for(int i = 1 ; i < n ; i ++) // i表示物品id
         for(int j = 0 ; j <= C ; j ++){
            memo[j] = memo[i-1][j];  // 之前的容量为j 的最大价值
            if(j >= w)
                  memo[j] = max(memo[j], v + memo[i - 1][j - w]);
         }
      return memo[n - 1][C];
}
};
六. 0-1背包问题的优化
时间复杂度优化空间不大, 但空间复杂度有优化空间
状态转移方程:
F(i,c) = max(F(i-1,c), v(i)+F(i-1,c-w(i)))

第i行元素依赖于第i-1行元素。理论上, 只要存储两行元素。
空间复杂度: O(2*c) = O(c)

过程如下(只有两行空间):
1.          i=0, i=1
2.          i=2, i=1
3.          i=2, i=3
4.          i=4, i=3
5.          ....

存储空间只要两行即可  前面一行处理偶数行, 后一行处理奇数行
改进代码
#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// 背包问题
/// 动态规划改进: 滚动数组
/// 时间复杂度: O(n * C) 其中n为物品个数; C为背包容积
/// 空间复杂度: O(C), 实际使用了2*C的额外空间
class Knapsack01{

public:
int knapsack01(const vector<int> &w, const vector<int> &v, int C){
      assert(w.size() == v.size() && C >= 0);
      int n = w.size();
      if( n == 0 && C == 0 )
         return 0;

      vector<vector<int>> memo(2, vector<int>(C + 1, 0));  //只要两行空间

      for(int j = 0 ; j <= C ; j ++)
         memo[0][j] = (j >= w[0] ? v[0] : 0);

      for(int i = 1 ; i < n ; i ++)
         for(int j = 0 ; j <= C ; j ++){
            memo[i % 2][j] = memo[(i-1) % 2][j];  // 利用奇偶
            if(j >= w)
                  memo[i % 2][j] = max(memo[i % 2][j], v + memo[(i-1) % 2][j - w]);
         }
      return memo[(n-1) % 2][C];
}
};
进一步优化
在后一行更新时，改为从容量最大的地方开始更新，会有一个特点:

假设后一行在更新容量为3的内容，
后一行只会参照前一行容量<=3的内容，
永远不会去看前一行容量>3的内容

后一行接着去更新容量为2的内容，
前一行容量>2的内容就不会去看了，所以即使不存储也可以

所以可以进一步优化，将开辟两行空间变为开辟一行空间  进行存储
代码
#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// 背包问题
/// 动态规划改进
/// 时间复杂度: O(n * C) 其中n为物品个数; C为背包容积
/// 空间复杂度: O(C), 只使用了C的额外空间
class Knapsack01{

public:
int knapsack01(const vector<int> &w, const vector<int> &v, int C){
      assert(w.size() == v.size() && C >= 0);
      intn = w.size();
      if(n == 0 || C == 0)
         return 0;

      vector<int> memo(C+1,0);  // 只需要开辟一行空间

      for(int j = 0 ; j <= C ; j ++)
         memo[j] = (j >= w[0] ? v[0] : 0);

      for(int i = 1 ; i < n ; i ++)
         for(int j = C ; j >= w ; j --) //如果 j < w i直接放不进背包了，所以不作考虑了
            memo[j] = max(memo[j], v + memo[j - w]);

      return memo[C];
}
};
七. 常见的0-1背包问题 Partition Equal Subset Sum
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意:

每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.
思路
其实就是典型的背包问题:  在n个物品中选出一定的物品, 填满容量为sum/2的背包

状态:
F(n, c) 考虑将n个物品填满容量为C的背包

状态转移方程:
F(i, c) = F(i-1,c) || F(i-1, c-w(i))

时间复杂度： O(n*sum/2)=O(n*sum)
代码
记忆化搜索
#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// 416. Partition Equal Subset Sum
///  ... et-sum/description/
/// 记忆化搜索
/// 时间复杂度: O(len(nums) * O(sum(nums)))
/// 空间复杂度: O(len(nums) * O(sum(nums)))
class Solution {

private:
// memo[c] 表示使用索引为[0...i]的这些元素,是否可以完全填充一个容量为c的背包
// -1 表示为未计算; 0 表示不可以填充; 1 表示可以填充
vector<vector<int>> memo;

// 使用nums[0...index], 是否可以完全填充一个容量为sum的背包
bool tryPartition(const vector<int> &nums, int index, int sum){

      if(sum == 0)
         return true;

      if(sum < 0 || index < 0)
         return false;

      if(memo[index][sum] != -1)
         return memo[index][sum] == 1;

      memo[index][sum] = (tryPartition(nums, index - 1, sum) ||
            tryPartition(nums, index - 1, sum - nums[index])) ? 1 : 0;

      return memo[index][sum] == 1;
}

public:
bool canPartition(vector<int>& nums) {

      int sum = 0;
      for(int i = 0 ; i < nums.size() ; i ++){
         assert(nums > 0);
         sum += nums;
      }

      if(sum % 2)  // 给定数组的和，必须可以被平分
         return false;

      memo.clear();
      for(int i = 0 ; i < nums.size() ; i ++)
         memo.push_back(vector<int>(sum / 2 + 1, -1));
      return tryPartition(nums, nums.size() - 1, sum / 2);
}
};
动态规划
#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// 416. Partition Equal Subset Sum
/// ... et-sum/description/
/// 动态规划
/// 时间复杂度: O(len(nums) * O(sum(nums)))
/// 空间复杂度: O(len(nums) * O(sum(nums)))
class Solution {

public:
bool canPartition(vector<int>& nums) {

      int sum = 0;
      for(int i = 0 ; i < nums.size() ; i ++){
         assert(nums > 0);
         sum += nums;
      }

      if(sum % 2)
         return false;

      int n = nums.size();
      int C = sum / 2;
      vector<bool> memo(C + 1, false);
      for(int i = 0 ; i <= C ; i ++)
         memo = (nums[0] == i); // 考虑第一个元素  是否可以填满背包

      for(int i = 1 ; i < n ; i ++)
         for(int j = C; j >= nums ; j --)
            memo[j] = memo[j] || memo[j - nums];

      return memo[C];
}
};

八. 最长上升子序列问题 Longest Increasing Subsequence
给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

解题思路
LIS(i)表示以第i个数字为结尾的最长上升子序列的长度

LIS(i)表示[0..j]的范围内，选择数字nums可以获得的最长上升子序列的长度

状态转移方程:
LIS(i) = max(1+LIS(j) if nums>nums[j])
      j<i

【即LIS(i)需要遍历所有<i的LIS,找出最大的LIS】




1. 一开始, 每个元素自身都是长度为了1的上升子序列
(第一行表示元素，第二行表示LIS(i), 因为是是初始化，每个LIS(i)=1)

10  9  2  5  3  7  101  18
1 1  1  1  1  1 1 1

2.
10  9  2  5  3  7  101  18
1 1  1  2  2  3 4 4
代码
动态规划
#include <iostream>
#include <vector>
using namespace std;

/// 300. Longest Increasing Subsequence
/// ... quence/description/
/// 动态规划
/// 时间复杂度: O(n^2)
/// 空间复杂度: O(n)
class Solution {

public:
int lengthOfLIS(vector<int>& nums) {

      if(nums.size() == 0)
         return 0;

      // memo 表示以 nums 为结尾的最长上升子序列的长度
      vector<int> memo(nums.size(), 1);
      for(int i = 1 ; i < nums.size() ; i ++)
         for(int j = 0 ; j < i ; j ++)
            if(nums > nums[j])
                  memo = max(memo, 1 + memo[j]);

      int res = memo[0];
      for(int i = 1 ; i < nums.size() ; i ++)
         res = max(res, memo);

      return res;
}
};
记忆化搜索(自顶向下的思路)
#include <iostream>
#include <vector>
using namespace std;

/// 300. Longest Increasing Subsequence
/// ... quence/description/
/// 记忆化搜索
/// 时间复杂度: O(n^2)
/// 空间复杂度: O(n)
class Solution {

private:
vector<int> memo;

// 以 nums[index] 为结尾的最长上升子序列的长度
int getMaxLength(const vector<int> &nums, int index){

      if(memo[index] != -1)
         return memo[index];

      int res = 1;
      for(int i = 0 ; i <= index-1 ; i ++)
         if(nums[index] > nums)
            res = max(res, 1 + getMaxLength(nums, i));

      memo[index] = res;
      return res;
}

public:
int lengthOfLIS(vector<int>& nums) {

      if(nums.size() == 0)
         return 0;

      memo = vector<int>(nums.size(), -1);
      int res = 1;
      for(int i = 0 ; i < nums.size() ; i ++)
         res = max(res, getMaxLength(nums, i));

      return res;
}
};
九. 最长公共子序列(LCS)
给出两个字符串S1和S2, 求这两个字符串的最长公共子序列的长度

S1 = ABCD
S2 = AEBD

最长公共子序列为: ABD
解题思路
LCS(m,n) 表示  S1[0..m]和S2[0...n] 的最长公共子序列

考虑两种情况：
1.  S1[m] == S2[n]: LCS(m,n) = 1 + LCS(m-1, n-1)
2.  S1[m] != S2[n]: LCS(m,n) = max( LCS(m-1,n), LCS(m, n-1) )
代码
记忆化搜索
#include <iostream>
#include <string>
#include <vector>
#include <cassert>

using namespace std;

/// LCS问题
/// 记忆化搜索
/// 时间复杂度: O(len(s1)*len(s2))
/// 空间复杂度: O(len(s1)*len(s2))
class LCS{

private:
vector<vector<int> > memo;

// 求s1[0...m]和s2[0...n]的最长公共子序列的长度值
int __LCS(const string &s1, const string &s2, int m, int n){

      if(m < 0 || n < 0)
         return 0;

      if(memo[m][n] != -1)
         return memo[m][n];

      int res = 0;
      if(s1[m] == s2[n])
         res = 1 + __LCS(s1, s2, m - 1, n - 1);
      else
         res = max(__LCS(s1, s2, m - 1, n),
                  __LCS(s1, s2, m, n - 1));
      memo[m][n] = res;
      return res;
}

// 通过memo反向求解s1和s2的最长公共子序列
string __getLCS(const string &s1, const string &s2){

      int m = s1.size() - 1;
      int n = s2.size() - 1;

      string res = "";
      while(m >= 0 && n >= 0)
         if(s1[m] == s2[n]){
            res = s1[m] + res;
            m --;
            n --;
         }
         else if(m == 0)
            n --;
         else if(n == 0)
            m --;
         else{
            if(memo[m-1][n] > memo[m][n-1])
                  m --;
            else
                  n --;
         }

      return res;
}

public:
string getLCS(const string &s1, const string &s2){

      memo.clear();
      for(int i = 0 ; i < s1.size() ; i ++)
         memo.push_back(vector<int>(s2.size(), -1));

      __LCS(s1, s2, s1.size() - 1, s2.size() - 1);
      return __getLCS(s1, s2);
}
};
动态规划
#include <iostream>
#include <string>
#include <vector>
#include <cassert>

using namespace std;

/// LCS问题
/// 动态规划
/// 时间复杂度: O(len(s1)*len(s2))
/// 空间复杂度: O(len(s1)*len(s2))
class LCS{

public:
string getLCS(const string &s1, const string &s2){

      int m = s1.size();
      int n = s2.size();

      // 对memo的第0行和第0列进行初始化
      vector<vector<int> > memo(m, vector<int>(n, 0));
      for(int j = 0 ; j < n ; j ++)
         if(s1[0] == s2[j]){
            for(int k = j ; k < n ; k ++)
                  memo[0][k] = 1;
            break;
         }

      for(int i = 0 ; i < m ; i ++)
         if(s1 == s2[0]){
            for(int k = i ; k < m ; k ++)
                  memo[k][0] = 1;
            break;
         }

      // 动态规划的过程
      for(int i = 1 ; i < m ; i ++)
         for(int j = 1 ; j < n ; j ++)
            if(s1 == s2[j])
                  memo[j] = 1 + memo[i-1][j-1];
            else
                  memo[j] = max(memo[i-1][j], memo[j-1]);

      // 通过memo反向求解s1和s2的最长公共子序列
      m = s1.size() - 1;
      n = s2.size() - 1;
      string res = "";
      while(m >= 0 && n >= 0)
         if( s1[m] == s2[n] ){
            res = s1[m] + res;
            m --;
            n --;
         }
         else if(m == 0)
            n --;
         else if(n == 0)
            m --;
         else{
            if(memo[m-1][n] > memo[m][n-1])
                  m --;
            else
                  n --;
         }

      return res;
}
};
优化
#include <iostream>
#include <string>
#include <vector>
#include <cassert>

using namespace std;

/// LCS问题
/// 动态规划, 躲避边界条件
/// 时间复杂度: O(len(s1)*len(s2))
/// 空间复杂度: O(len(s1)*len(s2))
class LCS{

public:
string getLCS(const string &s1, const string &s2){

      int m = s1.size();
      int n = s2.size();

      // memo 是 (m + 1) * (n + 1) 的动态规划表格
      // memo[j] 表示s1的前i个字符和s2前j个字符的最长公共子序列的长度
      // 其中memo[0][j] 表示s1取空字符串时, 和s2的前j个字符作比较
      // memo[0] 表示s2取空字符串时, 和s1的前i个字符作比较
      // 所以, memo[0][j] 和 memo[0] 均取0
      // 我们不需要对memo进行单独的边界条件处理 :-)
      vector<vector<int> > memo(m + 1, vector<int>(n + 1, 0));

      // 动态规划的过程
      // 注意, 由于动态规划状态的转变, 下面的i和j可以取到m和n
      for(int i = 1 ; i <= m ; i ++)
         for(int j = 1 ; j <= n ; j ++)
            if(s1[i - 1] == s2[j - 1])
                  memo[j] = 1 + memo[i - 1][j - 1];
            else
                  memo[j] = max(memo[i-1][j], memo[j-1]);

      // 通过memo反向求解s1和s2的最长公共子序列
      m = s1.size();
      n = s2.size();
      string res = "";
      while(m > 0 && n > 0)
         if( s1[m - 1] == s2[n - 1] ){
            res = s1[m - 1] + res;
            m --;
            n --;
         }
         else if(memo[m - 1][n] > memo[m][n - 1])
            m --;
         else
            n --;

      return res;
}
};

作者: 不二晨 时间: 2019-1-10 10:35

奈斯，加油

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2