动态规划问题解决的是最优化问题和计数问题。一个问题能否用动态规划解决，取决于它是否具备以下两个性质：

1. 重叠子问题
   一个大问题可以被分解成若干个小问题，而这些小问题会被重复计算多次。
2. 最优子结构
   一个大问题的最优解可以由其子问题的最优解推导出来。

步骤：

1. dp 状态表，一维/二维，取决于有几个影响参数
2. 推出状态转移方程，可能需要另一个状态，使用多个状态表
3. 初始化，防止数组越界
4. 遍历顺序
5. 计算返回值

简单多状态

122. 买卖股票的最佳时机 II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。然而，你可以在同一天多次买卖该股票，但要确保你持有的股票不超过一股。返回你能获得的最大利润

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // dp[i][j]:表示以i结尾的j(0:持有股票/1:不持有股票)种状态的最大利润
        // dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
        // dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2));
        // 初始化
        dp[0][0] = -prices[0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[n - 1][1];
    }
};

123. 买卖股票的最佳时机 III

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）

class Solution {
public:
    const int MIN = -0x3f3f3f3f;
    int maxProfit(vector<int>& prices) {
        // 持有：buy[i][j]:表示以i结尾的交易j次的最大利润
        // 不持有：sell[i][j]:表示以i结尾的交易j次的最大利润
        int n = prices.size();
        vector<vector<int>> buy(n, vector<int>(3, MIN)), sell(n, vector<int>(3, MIN));
        // 初始化
        buy[0][0] = -prices[0], sell[0][0] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                buy[i][j] = max(buy[i - 1][j], sell[i - 1][j] - prices[i]);
                sell[i][j] = sell[i - 1][j];
                if (j - 1 >= 0)
                    sell[i][j] = max(sell[i][j], buy[i - 1][j - 1] + prices[i]);
            }
        }
        return max(sell[n - 1][0], max(sell[n - 1][1], sell[n - 1][2]));
    }
};

子数组系列

152. 乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

/*
dp[i]
    |__ 长度为 1:nums[i]
    |__ 长度大于1：
        |__ nums[i] > 0:前面最大乘积 * nums[i]
        |__ nums[i] < 0:前面最小乘积 * nums[i]
*/
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        // dp[i]:以i结尾的最大乘积
        int n = nums.size();
        vector<int> f(n), g(n);
        f[0] = g[0] = nums[0];
        int ans = nums[0];
        for (int i = 1; i < n; i++) {
            if (nums[i] > 0) {
                f[i] = max(f[i - 1] * nums[i], nums[i]);
                g[i] = min(g[i - 1] * nums[i], nums[i]);
            } else {
                f[i] = max(g[i - 1] * nums[i], nums[i]);
                g[i] = min(f[i - 1] * nums[i], nums[i]);
            }
            ans = max(ans, max(f[i], g[i]));
        }
        return ans;
    }
};

子序列系列

子序列：由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列

300. 最长递增子序列

给你一个整数数组 nums，找到其中最长严格递增子序列的长度。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);
        // dp[i]:以i为结尾的最长长度
        int ans = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j])
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

回文串问题

01 背包

01 背包模板题 (opens new window)

#include <iostream>
#include <vector>

using namespace std;

// 不必装满
int PackageNotFull(vector<int>& worths, vector<int>& volumes, int n, int V) {
    vector<vector<int>> dp(n + 1, vector<int>(V + 1));
    // dp[i][j]表示前i个物品中，总体积不超过j时的最大总价值
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= V; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= volumes[i]) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - volumes[i]] + worths[i]);
            }
        }
    }
    return dp[n][V];
}

// 必须装满
int PackageFull(vector<int>& worths, vector<int>& volumes, int n, int V) {
    vector<vector<int>> dp(n + 1, vector<int>(V + 1));
    // dp[i][j]表示前i个物品中，总体积等于j时的最大总价值
    for (int i = 1; i <= V; i++) {
        dp[0][i] = -1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= V; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= volumes[i] && dp[i - 1][j - volumes[i]] != -1) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - volumes[i]] + worths[i]);
            }
        }
    }
    return dp[n][V] == -1 ? 0 : dp[n][V];
}


int main() {
    int n, V;
    cin >> n >> V;
    vector<int> worths(n + 1), volumes(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> volumes[i] >> worths[i];
    }
    cout << PackageNotFull(worths, volumes, n, V) << endl << PackageFull(worths,
            volumes, n, V) << endl;
    return 0;
}

优化：

#include <iostream>
#include <vector>

using namespace std;

// dp[i]表示：当背包容量为i时，能够获得的最大价值
int PackageNotFull(vector<int>& worths, vector<int>& volumes, int n, int V) {
    vector<int> dp(V + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = V; j >= volumes[i]; j--) {
            dp[j] = max(dp[j], dp[j - volumes[i]] + worths[i]);
        }
    }
    return dp[V];
}

int PackageFull(vector<int>& worths, vector<int>& volumes, int n, int V) {
    vector<int> dp(V + 1);
    for (int i = 1; i <= V; i++) dp[i] = -1;
    for (int i = 1; i <= n; i++) {
        for (int j = V; j >= volumes[i]; j--) {
            if (dp[j - volumes[i]] != -1) {
                dp[j] = max(dp[j], dp[j - volumes[i]] + worths[i]);
            }
        }
    }
    return dp[V] == -1 ? 0 : dp[V];
}


int main() {
    int n, V;
    cin >> n >> V;
    vector<int> worths(n + 1), volumes(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> volumes[i] >> worths[i];
    }
    cout << PackageNotFull(worths, volumes, n, V) << endl << PackageFull(worths,
            volumes, n, V) << endl;
    return 0;
}

完全背包