动态规划(dp)初步学习案例讲解

 问题(来源:leetcode300):

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

示例 2:

输入:nums = [0,1,0,3,2,3]
输出:4

 举例说明:

从上述案例nums可以看出(1 2 4)或者(1 2 3)都可以是最长的一个答案,而我们只要求出他的长度即可。

方案一,暴力穷举:

暴力穷举往往是最简单也最容易想到的,通过一步步逐步筛选,逐步搜索进行穷举。将其通过循环逐步套取,把每个子序列都进行一遍搜索,完成答案的求解,取最长数列长度即可。

通过一个getLen函数进行最长子序列的求取,需要注意的是,当i取到序列的最后一位时,返回长度1,停止搜索,而当你本身被搜索时就是一个长度单位,所以每次搜索的maxlen初始长度为1。

时间复杂度:假定数组长度为n,即可生成2^n个子序列(数组中的每个数字可以选择取用或者不取用两个方式,n个长度,即可为2^n个),每个子序列都需要进行n次遍历,即为O(n),所以时间 复杂度为O(2^n)*O(n)。

#include <iostream>
#include <algorithm> 
#include <cmath> 
#include <vector> 
#include <chrono>

using namespace std;

int getLen(vector<int> num, int i) {
    if (i == num.size() - 1) return 1;
    int maxlen = 1;
    for (int j = i + 1;j < num.size();j++) {
        if (num[j] > num[i]) {
            maxlen = max(maxlen, getLen(num, j) + 1);
        }
    }
    return maxlen;
}

int main() {
    auto start = chrono::high_resolution_clock::now(); // 记录开始时间
    int nums[25] = { 1,5,2,4,3,7,15,35,61,2,58,64,9,15,3,44,12,33,65,15,22,49,85,2,34};
    int ans = 0;
    vector<int> num(nums, nums +25);
    for (int i = 0;i < num.size();i++) {
        ans = max(ans, getLen(num, i));
    }
    cout << ans << endl;
    auto end = chrono::high_resolution_clock::now(); // 记录结束时间
    auto duration = chrono::duration_cast<chrono::microseconds>(end - start); // 计算程序运行时间
    cout << "程序运行时间:" << duration.count() << "微秒" << endl;
    return 0;
}

算法优化:空间换时间

方案二,用哈希进行回溯剪枝:

由于在暴力穷举的过程中,存在当你访问过一个数据时又一次访问该数据,即如图,第一次在(1 2 4)中已经检索过4,而在后续过程中又一次访问了4(1 4),即可用空间来换取时间,创建一个哈希表进行记录存储最大子序列长度,即可减少访问步骤。

依然是通过getLen方法来获取最大子序列长度,不过本次加入了memo哈希表来进行数据存储,当memo中数据非0时,即表明该处内容已被检索,即可直接返回memo[i],减少搜索时间。

 时间复杂度大大减少

#include <iostream>
#include <algorithm> 
#include <cmath> 
#include <vector> 
#include <chrono>

using namespace std;
vector<int> memo(25);

int getLen(vector<int> num, int i) {
    if (i == num.size() - 1) return 1;
    if (memo[i] != 0) return memo[i];
    int maxlen = 1;
    for (int j = i + 1;j < num.size();j++) {
        if (num[j] > num[i]) {
            maxlen = max(maxlen, getLen(num, j) + 1);
        }
    }
    memo[i] = maxlen;
    return maxlen;
}

int main() {
    auto start = chrono::high_resolution_clock::now(); // 记录开始时间
    int nums[25] = { 1,5,2,4,3,7,15,35,61,2,58,64,9,15,3,44,12,33,65,15,22,49,85,2,34 };
    int ans = 0;
    vector<int> num(nums, nums + 25);
    for (int i = 0;i < num.size();i++) {
        ans = max(ans, getLen(num, i));
    }
    cout << ans << endl;
    auto end = chrono::high_resolution_clock::now(); // 记录结束时间
    auto duration = chrono::duration_cast<chrono::microseconds>(end - start); // 计算程序运行时间
    cout << "程序运行时间:" << duration.count() << "微秒" << endl;
    return 0;
}

方案三,改写成迭代形式:

通过反推的方式,从序列最后一位开始寻找最长子序列,逐步倒推归纳迭代,一直访问到第一位时的最长子序列,即可完成数据的搜寻访问。

实现方式:通过getLen方法来获取子序列最长长度,通过倒序搜索来寻找子序列中各自的最长数组长度,i从倒数第二位开始访问,由于倒数第一位一定是1,一直搜索到第一位,而j则是通过i+1到最后一位进行搜索,在找完各自的最长数组后,进行排序,找出最大值即可。

时间复杂度: 由于只进行了两个循环,即为O(n^2)。

#include <iostream>
#include <algorithm> 
#include <cmath> 
#include <vector> 
#include <chrono>

using namespace std;

int getLen(vector<int> num) {
    int n = num.size();
    vector<int> L(n,1);
    for (int i = n-2;i>=0;i--) {
        for (int j = i + 1;j < n;j++) {
            if (num[j] > num[i]) L[i] = max(L[i], L[j] + 1);
        }
    }
    sort(L.begin(), L.end());
    return L[n-1];
}

int main() {
    auto start = chrono::high_resolution_clock::now(); // 记录开始时间
    int nums[25] = { 1,5,2,4,3,7,15,35,61,2,58,64,9,15,3,44,12,33,65,15,22,49,85,2,34 };
    int ans = 0;
    vector<int> num(nums, nums + 25);
    cout << getLen(num) << endl;
    auto end = chrono::high_resolution_clock::now(); // 记录结束时间
    auto duration = chrono::duration_cast<chrono::microseconds>(end - start); // 计算程序运行时间
    cout << "运行时间:" << duration.count() << "微秒" << endl;
    return 0;
}

 动态规划思路总结:

  1.  使用穷举法完成暴力搜索,可画出递归树
  2. 在搜索过程中发现重复搜索的痕迹,即可用哈希表进行数据回溯剪枝
  3. 将计算的过程用迭代的方式表示出来