不会吧不会吧，还有人学了三五遍还是不会动态规划算法？快戳 –>>

一、简单引入 · 斐波那契的例子

举个例子：计算斐波那契数列（1，1，2，3，5，…）的第n项

1. 暴力法（递归）
1
2
3
4
int Fibonacci(int n) {
    if (n == 1 || n == 2) return 1;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

但这是一个非常低效的办法。我们评判递归算法的性能一般采用递归树，那让我们画出上面算法的递归树：

image-20210116122611516

可以发现有很多的结点是在重复计算的，比如 f(3)。于是我们可以采用备忘录的方式（或者哈希字典）进行优化：

2. 备忘录方式
1
2
3
4
5
6
7
8
9
10
11
12
13
int helper (vector<int>& memo, int n);
int Fibonacci2(int n) {
    vector<int> memo(n + 1, 0); // 初始化为全0
    return helper(memo, n);
}
int helper (vector<int>& memo, int n) {
    if (n == 1 || n == 2) return 1;
    if (memo[n] != 0) return memo[n]; // 如果备忘录中已经有了就不需要重复计算
    else {
        memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
        return memo[n];
    }
}

执行结果对比：

image-20210114161735768

可以发现，在数据量大的情况下（截图中为 f(40)），两种方法的效率有着质的差别。

在备忘录方法下，算法的时间复杂度又如何？以 f(40) 为例，算法只需要计算从 f(1) 到 f(40) ，所以 时间复杂度为 O(N) 。相比于暴力算法的时间复杂度 O($2^N$) 而言，这波空间换时间是超值了！

3. 动态规划

动态规划方法就是把“备忘录”独立出来，成为 DP_table，完成自底向上的计算。

1
2
3
4
5
6
7
8
9
int Fibonacci3(int n) {
    if (n == 1 || n == 2) return 1;
    vector<int> fib(n + 1);  // DP_table（dp数组）
    fib[1] = 1; fib[2] = 1;
    for (int i = 3; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];  // 状态转移方程
    }
    return fib[n];
}

其实斐波那契问题严格来说不算动态规划问题，毕竟没有涉及最优子问题。

二、第一个例子 · 凑零钱问题

有两种面值的纸币，2元、3元，每种纸币数量不限。
问：对于总额 amount，最少需要多少纸币才能凑出？若不能，返回 -1.

这给问题是一个典型的动态规划问题，因为他具有最优子结构。对于总额为 amount 时的最优方案，必然要求当总额为 amount - 2 和 amount - 3 时也是最优的，并且 changes[amount] = min(changes[amount - 2], changes[amount - 3]) + 1;。

此处 dp 数组 changes[amount] = n 的涵义为：当总额为 amount 时，最优解为 n ，即最少需要 n 张纸币才能凑出面额。

状态转移方程的数学表达式为：

$changes(amount) = \begin{cases} -1, & \text{当 $amount$ = 1} \\ 1, & \text{当 $amount$ = 2 或 3} \\ min{changes[amount - 2], changes[amount - 3]} + 1, & \text{当 $amount$ > 3} \end{cases}$

1
2
3
4
5
6
7
8
9
10
11
12
int changes(int amount) {
    vector<int> changes(amount + 1);
    if (amount == 1) return -1;
    if (amount == 2 || amount == 3) return 1;
    changes[1] = INT_MAX;
    changes[2] = 1;
    changes[3] = 1;
    for (int i = 4; i <= amount; i++) {
        changes[i] = min(changes[i - 2], changes[i - 3]) + 1; // 状态转移方程
    }
    return changes[amount] == INT_MAX? -1 : changes[amount];
}

三、动态规划简介

动态规划（dynamic programming）和分治方法相似，都是通过组合子问题来解决原问题。
分治方法将问题划分为互不相交的子问题，递归地求解子问题，再将他们组合起来，求出原问题的解。与之相反，动态规划应用于问题重叠的情况，即不同的子问题具有公共的子子问题。动态规划对每个子子问题只求解一次，将结果保存在表格中，减少了重复计算的工作。

—— 摘编自《算法导论》

一般我们可以从两个方面来判断一个问题能否用动态规划求解：

  1. 是否是最优解问题
  2. 能否分解为相互重叠的最优子问题

然后，

  1. 定义 dp 数组的具体含义

  2. 根据具体情况推导出状态转移方程，自底向上地进行解决。

四、Leetcode 动态规划 · 股票系列

1. 买股票的最佳时机（一）

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。

思路：股票问题的方法就是 动态规划，因为它包含了重叠子问题，即买卖股票的最佳时机是由之前买或不买的状态决定的，而之前买或不买又由更早的状态决定的。这题只需要做一次买卖，相对而言比较简单，可以不用动态规划，直接靠逻辑推理做出。我们将给出以上的两种办法。

逻辑推理法

首先，获得最大利润意味着我们希望在最小值处买入，在最大值处卖出。但需要明确，只有在买入以后才能卖出，可以卖出的前提是需要已经买入。所以，用更精炼的语言来说，我们希望在历史最低点买入，最高点卖出。因此，我们可以维护两个变量，分别为历史低价和最大差价，遍历每一个数据，不断更新历史低价和最大差价，最后输出最大差价。

1
2
3
4
5
6
7
8
9
10
11
int maxProfit(vector<int>& prices) {
    int n = prices.size();
    if (n == 0) return 0; // 边界条件
    int minprice = prices[0];
    int maxprofit = 0;
    for (int i = 1; i < n; i++){
        maxprofit = max(maxprofit, prices[i] - minprice); // 维护最大差价
        minprice = min(minprice, prices[i]);  // 维护历史低价
    }
    return maxprofit;
}
动态规划法

我们用 dp 数组 maxprofit[i] 表示至 i 天的最大利润。那么我们可以列出状态转移方程：$maxprofit[i] = max\{maxprofit[i - 1], price[i] - minprice\}$。即至 i 天的最大利润只能是
$\begin{cases} 至 i- 1 天的最大利润：（第 i 天下跌了） \\ 当天价格 - 历史最低价：（第 i 天上涨了） \end{cases}$

1
2
3
4
5
6
7
8
9
10
11
int maxProfit(vector<int>& prices) {
    int n = prices.size();
    if (n == 0) return 0; // 边界条件
    int minprice = prices[0];
    vector<int> maxprofit (n, 0);
    for (int i = 1; i < n; i++){
        minprice = min(minprice, prices[i]); // 维护历史低价
        maxprofit[i] = max(maxprofit[i - 1], prices[i] - minprice);
    }
    return maxprofit[n - 1];
}

2.买卖股票的最佳时机（二）

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii

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

同样这题较为简单，可以用逻辑推理和动态规划两种方法完成。

逻辑推理法

题目允许不限次数的交易，所以我们希望每次在价格开始上升的节点买入，在价格开始下降的节点卖出。但如果用变量来记录买入和卖出的状态会稍有繁琐，这里有一个本质上一样但在实现上更加美观简洁的理解：每当次日的价格较前日上涨，则累计增幅，最终累计的和就是题目要求的最大利润。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
        int maxProfit = 0;
        for (int i = 0; i < prices.size() - 1; i++) {
            if (prices[i] < prices[i + 1]) {
                maxProfit = maxProfit + prices[i + 1] - prices[i];
            } 
        }
        return maxProfit;
    }
};
动态规划法

对于第 n - 1 天有两个状态：持有、未持有。对于持有状态，我们可以有两种操作：卖出、继续持有。对于未持有状态，我们可以有两种操作：保持不持有、买入。（此处 income[n] 为第 n 天最大收入）

第 n 天 $\begin{cases} 持有\begin{cases} （第n - 1天可能的情况）持有：income[n - 1] \\（第n - 1天可能的情况）不持有，在第 n 天买入：income[n - 1] - price[n] \end{cases} \\ 未持有\begin{cases} （第n - 1天可能的情况）不持有：income[n - 1] \\ （第n - 1天可能的情况）持有，在第 n 天卖出：income[n - 1] + price[n] \end{cases} \end{cases}$

我们定义状态 profit[i][] 的第二个维度为完成第 i 天的交易后是否持有股票。即 profit[i][0] 表示完成第 i 天的交易后不持有股票。

因此我们可以写出状态转移方程：

$\begin{cases} profit[i][0] = max\{profit[i - 1][0], profit[i - 1][1] + prices[i]\} \\profit[i][1] = max\{profit[i - 1][1], profit[i - 1][0] - prices[i]\} \end{cases}$

1
2
3
4
5
6
7
8
9
10
int maxProfit(vector<int>& prices) {
    int n = prices.size();
    int profit[n][2];
    profit[0][0] = 0, profit[0][1] = -prices[0];
    for (int i = 1; i < n; i++) {
        profit[i][0] = max(profit[i - 1][0], profit[i - 1][1] + prices[i]);
        profit[i][1] = max(profit[i - 1][1], profit[i - 1][0] - prices[i]);
    }
    return profit[n - 1][0];
}

3.买卖股票的最佳时机（三）

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/

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

思路：使用动态规划的办法。

二维dp表法

对于每一天有五个操作：$\begin{cases} state=0：没有操作 \\state=1：第一次买入 \\state=2：第一次卖出 \\state=3：第二次买入 \\state=4：第二次卖出 \end{cases}$

我们令 dp 表 profit[n][state] 表示第 n 天处于 state 状态时的最大利润。这五个状态和前一天的联系如下图所示：

$\begin{cases} state=0：没有操作 \\state=1：第一次持有\begin{cases} 当天买入：profit[n-1][0]-price[n] \\此前已经买入：price[n-1][1] \end{cases} \\state=2：第一次卖出\begin{cases} 当天卖出：profit[n-1][1]+price[n] \\此前已经卖出：profit[n-1][2] \end{cases} \\state=3：第二次买入\begin{cases} 当天买入：profit[n-1][2]-price[n] \\此前已经买入：price[n-1][3] \end{cases} \\state=4：第二次卖出\begin{cases} 当天卖出：profit[n-1][3]+price[n] \\此前已经卖出：profit[n-1][4] \end{cases} \end{cases}$

所以我们可以写出状态转移方程：

$\begin{cases} profit[0][0] = 0 \\profit[n][1] = max\{profit[n - 1][0] - price[n], profit[n - 1][1]\} \\profit[n][2] = max\{profit[n - 1][1] + price[n], profit[n - 1][2]\} \\profit[n][3] = max\{profit[n - 1][2] - price[n], profit[n - 1][3]\} \\profit[n][4] = max\{profit[n - 1][3] + price[n], profit[n - 1][4]\} \end{cases}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int maxProfit(vector<int>& prices) {
    if (prices.size() == 0) return 0;
    vector<vector<int>> profit(prices.size(), vector<int>(5, 0));
    profit[0][0] = 0;
    profit[0][1] = -prices[0];
    profit[0][3] = -prices[0];
    for (int i = 1; i < prices.size(); i++) {
        profit[i][0] = profit[i - 1][0];
        profit[i][1] = max(profit[i - 1][1], profit[i - 1][0] - prices[i]);
        profit[i][2] = max(profit[i - 1][2], profit[i - 1][1] + prices[i]);
        profit[i][3] = max(profit[i - 1][3], profit[i - 1][2] - prices[i]);
        profit[i][4] = max(profit[i - 1][4], profit[i - 1][3] + prices[i]);
    }
    return profit[prices.size() - 1][4];
}
一维dp表法

很显然，上一个办法使用了二维数组作为辅助空间，是一笔不小的空间开销。我们思考：能不能使用一维数组作为 dp 表呢？很容易发现在上个方法的状态转移方程中，第 i 天的值只和第 i - 1 天的相关，于是我们无需保存历史数据，只需要设置四个变量维护四种状态的最新值：

$\begin{cases} buy1：只进行过一次买操作 \\sell1：在一次买入后卖出 \\buy2：第二次买入 \\sell2：完成全部两笔操作 \end{cases}$

我们可以得到状态转移方程

$\begin{cases} buy1 = max\{buy1’, -price[i]\} \\sell1 = max\{sell1’,buy1’+price[i]\} \\buy2 = max\{buy2’, sell1’-price[i]\} \\sell2=max\{sell2’, buy2’+price[i]\} \end{cases}$

最后我们返回的值应该是 sell2 。因为首先最大利润一定是卖出状态，只能是 sell1 或者 sell2。如果最优解恰好是只完成一次交易即 sell1，也可以通过在最后一天买入并卖出转化成 sell2。

1
2
3
4
5
6
7
8
9
10
11
12
int maxProfit(vector<int>& prices) {
    int n = prices.size();
    int buy1 = -prices[0], sell1 = 0;
    int buy2 = -prices[0], sell2 = 0;
    for (int i = 1; i < n; ++i) {
        buy1 = max(buy1, -prices[i]);
        sell1 = max(sell1, buy1 + prices[i]);
        buy2 = max(buy2, sell1 - prices[i]);
        sell2 = max(sell2, buy2 + prices[i]);
    }
    return sell2;
}

4.买卖股票的最佳时机（四）

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/

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

通过前三题的练习，不难想到可以根据题意列出 2*k + 1种状态，分别为：

$\begin{cases} state = 0：没有任何操作 \\state = 1：第一次买入\begin{cases}第n天买入：profit[n-1][0] - price[n] \\此前已经买入：profit[n-1][1] \end{cases} \\state = 2：第一次卖出\begin{cases}第n天卖出：profit[n-1][1] + price[n] \\此前已经卖出：profit[n-1][2] \end{cases} \\state = 3：第二次买入\begin{cases}第n天买入：profit[n-1][2] - price[n] \\此前已经买入：profit[n-1][3] \end{cases} \\state = 4：第二次卖出\begin{cases}第n天卖出：profit[n-1][3] + price[n] \\此前已经卖出：profit[n-1][4] \end{cases} \\…… \\state = 2k - 1：第k次买入\begin{cases}第n天买入：profit[n-1][2k-2] - price[n] \\此前已经买入：profit[n-1][2k-1] \end{cases} \\state = 2k：第k次卖出\begin{cases}第n天卖出：profit[n-1][2k-1] + price[n] \\此前已经卖出：profit[n-1][2k] \end{cases} \end{cases}$

很容易得到状态转移方程：
$\begin{cases} profit[n][2i-1] = max\{profit[n-1][2i-2] - price[n], profit[n-1][2i-1]\} \\profit[n][2i-2] = max\{profit[n-1][2i-1] + price[n], profit[n-1][2i-2]\} \end{cases}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int maxProfit(int k, vector<int>& prices) {
    if (prices.size() == 0) return 0;
    vector<vector<int>> profit(prices.size(), vector<int>(2 * k + 1, 0));
    profit[0][0] = 0;
    for (int i = 1; i < 2 * k + 1; i = i + 2) {
        profit[0][i] = -prices[0];
    }
    for (int i = 1; i < prices.size(); i++) {
        for (int j = 1; j < 2 * k + 1; j = j + 2) { // 处理所有的买入状态
            profit[i][j] = max(profit[i - 1][j], profit[i - 1][j - 1] - prices[i]);
        }
        for (int j = 2; j < 2 * k + 1; j = j + 2) { // 处理所有的卖出状态
            profit[i][j] = max(profit[i - 1][j], profit[i - 1][j - 1] + prices[i]);
        }
    }
    return profit[prices.size() - 1][2 * k];
}

5.最佳买卖股票时机含冷冻期

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

虽然题目很花哨，首先仍旧是确定状态：

对于第 n 天有两个状态：持有、未持有。对于持有状态，我们可以有两种操作：卖出、继续持有。对于未持有状态，我们可以有两种操作：保持不持有、买入。（此处 income[n] 为第 n 天最大收入）

第 n 天 $\begin{cases} 持有\begin{cases} 之前已经买入：income[n - 1] \\在第 n 天买入：income[n - 2] - price[n] \end{cases} \\ 未持有\begin{cases} 之前已经卖出：income[n - 1] \\在第 n 天卖出：income[n - 1] + price[n] \end{cases} \end{cases}$

上图中 n - 2 的含义是：考虑冷冻期，若要第 n 天进行买入操作，则第 n - 1 天必定不能进行卖出操作，income[n - 1] = income[n - 2];

我们定义状态 profit[i][] 的第二个维度为完成第 i 天的交易后是否持有股票。即 profit[i][0] 表示完成第 i 天的交易后不持有股票。

因此我们可以写出状态转移方程：

$\begin{cases} profit[i][0] = max\{profit[i - 1][0], profit[i - 2][1] + prices[i]\} \\profit[i][1] = max\{profit[i - 2][1], profit[i - 1][0] - prices[i]\} \end{cases}$

在下述代码中，笔者希望提醒各位读者重视初始值的设置以及边界的特殊处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int maxProfit(vector<int>& prices) {
    int n = prices.size();
    if (n == 0 || n == 1) return 0;
    int profit[n][2];
    // 初始值设定
    profit[0][0] = 0, profit[0][1] = -prices[0];
    profit[1][0] = max(0, prices[1] - prices[0]), profit[1][1] = max(-prices[0], -prices[1]);
    // 迭代 dp 表 profit[][]
    for (int i = 2; i < n; i++) {
        profit[i][0] = max(profit[i - 1][0], profit[i - 1][1] + prices[i]);
        profit[i][1] = max(profit[i - 1][1], profit[i - 2][0] - prices[i]);
    }
    return profit[n - 1][0];
}

6.买卖股票的最佳时机含手续费

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费

本题中，手续费是一件比较难处理的问题。该在算法的何时扣除手续费？不妨按三种情况思考：1.买入时一次性扣除；2.卖出时一次性扣除；3.买入时扣除一半，卖出时扣除一半。

笔者不才，难以用逻辑推理的方式选择方案，将上述三种情况分别做了实现。其中对买入时一次性扣除方案做了详细阐述。

买入时一次扣除

首先仍旧是确定状态：

对于第 n 天有两个状态：持有、未持有。对于持有状态，我们可以有两种操作：卖出、继续持有。对于未持有状态，我们可以有两种操作：保持不持有、买入。（此处 income[n] 为第 n 天最大收入）

第 n 天 $\begin{cases} 持有\begin{cases} 之前已经买入：income[n - 1] \\在第 n 天买入：income[n - 1] - price[n] - fee \end{cases} \\ 未持有\begin{cases} 之前已经卖出：income[n - 1] \\在第 n 天卖出：income[n - 1] + price[n] \end{cases} \end{cases}$

我们定义状态 profit[i][] 的第二个维度为完成第 i 天的交易后是否持有股票。即 profit[i][0] 表示完成第 i 天的交易后不持有股票。

因此我们可以写出状态转移方程：

$\begin{cases} profit[i][0] = max\{profit[i - 1][0], profit[i - 1][1] + prices[i]\} \\profit[i][1] = max\{profit[i - 1][1], profit[i - 1][0] - prices[i] - fee\} \end{cases}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int maxProfit(vector<int>& prices, int fee) {
    int n = prices.size();
    if (n == 0 || n == 1) return 0;
    int profit[n][2]; 
    // 初始值设定
    profit[0][0] = 0, profit[0][1] = -prices[0] - fee;
    profit[1][0] = max(0, prices[1] - prices[0] - fee), profit[1][1] = max(-prices[0] - fee, -prices[1] - fee);
    // 迭代 dp 表 profit[][]
    for (int i = 2; i < n; i++) {
        profit[i][0] = max(profit[i - 1][0], profit[i - 1][1] + prices[i]);
        profit[i][1] = max(profit[i - 1][1], profit[i - 1][0] - prices[i] - fee);
    }        
    return profit[n - 1][0];
}

经过验证，结果正确。

卖出时一次性扣除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int maxProfit(vector<int>& prices, int fee) {
    int n = prices.size();
    if (n == 0 || n == 1) return 0;
    int profit[n][2]; 
    // 初始值设定
    profit[0][0] = 0, profit[0][1] = -prices[0];
    profit[1][0] = max(0, prices[1] - prices[0] - fee), profit[1][1] = max(-prices[0], -prices[1]);
    // 迭代 dp 表 profit[][]
    for (int i = 2; i < n; i++) {
        profit[i][0] = max(profit[i - 1][0], profit[i - 1][1] + prices[i] - fee);
        profit[i][1] = max(profit[i - 1][1], profit[i - 1][0] - prices[i]);
    }        
    return profit[n - 1][0];
}

经过验证，结果正确。

买入时扣除一半，卖出时扣除一半

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int maxProfit(vector<int>& prices, int fee) {
    int n = prices.size();
    if (n == 0 || n == 1) return 0;
    double profit[n][2];
    // 初始值设定
    profit[0][0] = 0;
    profit[0][1] = -prices[0] - fee/2.0;
    profit[1][0] = max(0.0, prices[1] - prices[0] - fee/1.0);
    profit[1][1] = max(-prices[0] - fee/2.0, -prices[1] - fee/2.0);
    // 迭代 dp 表 profit[][]
    for (int i = 2; i < n; i++) {
        profit[i][0] = max(profit[i - 1][0], profit[i - 1][1] + prices[i] - fee/2.0);
        profit[i][1] = max(profit[i - 1][1], profit[i - 1][0] - prices[i] - fee/2.0);
    }
    return profit[n - 1][0];
}

经过验证，结果正确。

这个方法存在一定的坑点：

  1. 通常我们在这题的题干下习惯将 fee 的类型设置为 int，若不加注意，在本题 fee / 2 时如产生小数将会对结果进行舍入，导致答案出错。例如：在高级编程语言整数除法的约定下，想必各位i读者对 3 / 2 = 1 应该不陌生。

  2. 若考虑到了坑点1所述的问题，但将 profit[][] 的类型设置为float，在较大整数下会出现问题：在32位机器下，有符号int类型是32位，即有效位数为31位；float类型小数部分为23位，对于超过24位的有符号Int类型转float，将会进行舍入。

    类型 数符 阶码 尾数数值 总位数 偏置值（十进制） 偏置值（十进制）
    短浮点数 1 8 23 32 127 7FH
    长浮点数 1 11 52 64 1023 3FFH
    临时浮点数 1 15 64 80 16383 3FFFH

    显而易见，如使用 double 类型则可以满足有符号 int 类型的位数需求。以上“位数”均为机器数位数）

五、总结

如果遇到的问题是求最优解问题，并且存在重叠子问题，则可以考虑使用动态规划算法求解。

是用动态规划方法，重中之重是定义状态，写出状态转移转移方程

至此，便可以开始着手编写程序代码。

在此笔者尤其想提醒各位读者：不要轻视 dp 数组初始值的设定和对于给定参数边界值的处理！

写在最后：本文是笔者在经历了几次动态规划问题的学习之后，参考部分资料并结合自己的理解，整理出的一篇动态规划入门学习文章。对于第四章所举的例子，目的为利用相近情境的题目提升趣味性，可能覆盖的方法与技巧不够全面，后续可能会进行修改。如有疏漏，欢迎读者在评论区指正！

参考资料：leetcode 平台（https://leetcode-cn.com/），书籍《labuladong的算法小抄》《算法导论（第三版）》《算法笔记》，以及网络各类资料。