一文彻底弄懂动态规划【DP】

在这里插入图片描述

动态规划是一种重要的算法，它能解决很多看似复杂的问题，关键在于找到问题的子问题结构，并根据子问题的解决方式来解决原问题。首先要了解的是动态规划的基本思想：

动态规划的基本思想是：将一个复杂的问题分解为一系列相关的子问题，每个子问题只解决一次，并将结果储存在一个可以查找的数据结构中（通常是一个数组或表格）。当要解决相同的子问题时，不需要重新计算，而是可以直接从表格中获取已经计算过的结果。这种使用了额外的存储空间来节省计算时间的方法，常被称为空间换时间。动态规划关键在于如何定义子问题和状态，如何寻找和计算状态转移。

动态规划主要包含三个步骤：

定义状态：状态可以看做是原问题的子问题，通常是对应的一个或多个变量。例如，在背包问题中，状态就是当前放入背包的物品的总价值。
状态转移方程：状态转移方程描述了状态之间的关系。例如，在背包问题中，当前的总价值可以由之前的物品价值和当前物品的价值得出。
初始化和边界条件：动态规划解决问题时，需要一个初始状态作为问题的起点，并在问题解决的过程中处理好边界条件。

下面介绍五个经典的动态规划问题，以及它们的解决思路和代码表示：

斐波那契数列

这是最简单的动态规划问题，它描述的是一种特殊的数列：F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2) (n>=2)，要求出第n项的数值。

解题思路：假设dp[i]表示第i个斐波那契数，状态转移方程为dp[i] = dp[i-1] + dp[i-2]。

vector<int> fib(int N) {
    vector<int> dp(N+1, 0);
    dp[0] = 0; // 初始化
    dp[1] = 1; // 初始化
    for(int i = 2; i <= N; i++){
        dp[i] = dp[i-1] + dp[i-2]; // 状态转移方程
    }
    return dp[N];
}

凑零钱问题

这是一种找零问题，给定不同面额的硬币和一个总金额，每种硬币的数量无限，求出能拼凑出总金额所需的最少的硬币个数。

解题思路：假设dp[i]表示拼出金额i所需的最少硬币个数，状态转移方程为dp[i] = min(dp[i], dp[i-coin]+1)其中coin为所有硬币面额。

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

最长公共子序列

给出两个字符串，求出他们的最长公共子序列的长度。

解题思路：假设dp[i][j]表示字符串1的前i个字符和字符串2的前j个字符的最长公共子序列的长度，当str1[i]==str2[j]时，dp[i][j]等于dp[i-1][j-1]+1，否则等于max(dp[i-1][j], dp[i][j-1])。

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.length(), n = text2.length();
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            if(text1[i-1] == text2[j-1]){
                dp[i][j] = dp[i-1][j-1] + 1;
            }
            else{
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[m][n];
}

0-1背包问题

这是一种很经典的动态规划问题，给定一组物品的重量和价值，一个能承受最大重量的背包，求出能装入背包的物品的最大价值。

解题思路：假设dp[i][j]表示前i个物品重量不超过j的最大价值，状态转移方程为dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])。

int knapsack(vector<int>& weight, vector<int>& value, int W) {
    int n = weight.size();
    vector<vector<int>> dp(n+1, vector<int>(W+1, 0));
    
    for(int i = 1; i <= n; i++){
        for(int j = W; j >= 1; j--){
            if(j >= weight[i-1]){
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i-1]] + value[i-1]);
            }
            else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[n][W];
}

最长递增子序列

给出一个无序的整数数组，求出它的最长递增子序列的长度。

解题思路：假设dp[i]表示以第i个数字结尾的最长上升子序列长度，状态转移方程为dp[i] = max(dp[i], dp[j] + 1)(对所有0<=j<i，如果nums[i]>nums[j])。

int lengthOfLIS(vector<int>& nums) {
    if (nums.empty())
        return 0;
    vector<int> dp(nums.size(), 1);
    int res = 1;
    for (int i = 1; i < nums.size(); ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        res = max(res, dp[i]);
    }
    return res;
}