​​点击阅读更多查看文章内容

算法笔记——动态规划

动态规划是一个非常灵活的算法，动态规划本身不难，无非就是一个状态转移的过程，难点就在于我们该如何去定义“状态”，而这就需要我们多做题来积累经验，这也是初学者遇到动态规划往往无从下手的原因。

动态规划的核心在于状态和状态转移方程，状态具体该如何去定义，需要大家多做题来体会，下面主要是记录一下动态规划的一般解题思路。

以122. 买卖股票的最佳时机 II为例
给定一个数组 prices ，其中 prices[i] 表示股票第 i 天的价格。
在每一天，你可能会决定购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以购买它，然后在同一天出售。
返回你能获得的最大利润 。

1.将原问题分解为若干子问题

这一步是为后续的状态定义做一个铺垫，注意分解的子问题一定要是连续的并且可以递推求得原问题的解，且分解的子问题一定要保证不能遗漏（有些情况下可以重复，比如求最大值，有些情况下不能重复，比如求序列和——重复的话就会有元素被用了两次）
问题中是要求我们最终所能获得的最大利润，我们可以将其分解为截止到第一天所能获得的最大利润、截止到第二天所能所能获得的最大利润……截止到最后一天所能获得的最大利润，这样我们就将原来的问题分解为一系列的子问题

2.根据子问题定义状态

根据第一步分解得到的子问题，我们可以根据其进行状态的定义了，状态其实就是对子问题的一种表示，状态的值就是我们所要求的解
我们假设截止到第i天所能获得的最大利润为w，问题中还有一句话你在任何时候最多只能持有一股股票，由此我们可以用一个二维数组dp[][]来表示状态，第一维表示是第几天，第二维则表示你当前是否持有股票，我们可以用0表示没有股票，1表示有股票。
综上，状态定义为：dp[i][0]->截止到第i天没有股票所能获得的最大利润；dp[i][1]->截止到第i天有股票所能获得的最大利润

3.确定边界条件

所谓边界条件就是状态转移方程的初始条件或终止条件
本问题中边界条件就是第1天的状态，第一天没有股票的话就是没有买也没有卖股票所获利润为dp[1][0]=0，第1天有股票的话就是在第一天买了一股股票此时因为没有卖出所以利润为dp[1][1]=-prices[1]

4.确定状态转移方程

状态转移方程就是在确定得到当前状态的方法，即如何从一个已经求出的状态得到当前的状态，并最终递推得到最终值，状态转移方程是根据状态来定的。
本题中第i天的状态为dp[i][0]和dp[i][1]，我们要找到从第i天到第i+1天的状态转移方程，注意题目中在每一天，你可能会决定购买和/或出售股票，我们在每一天可能发生的动作有购买/出售和不做任何操作三种
首先考虑dp[i+1][0]，即第i+1天没有股票的状态，可能的状态转移方程有第i天没有股票，第i+1天不做任何操作；第i天有股票，第i+1天卖出了股票，最大的利润就是这两种转移方程的最大值，表示成代码为：dp[i+1][0]=max(dp[i][0],dp[i-1][1]+prices[i+1])
然后考虑dp[i+1][1]，第第i+1天有股票的状态，可能的状态转移方程有第i天没有股票，第i+1天买入了股票；第i天有股票，第i+1天不做任何操作最大的利润就是这两种转移方程的最大值，表示成代码为：dp[i+1][1]=max(dp[i][0]-prices[i+1],dp[i][1])

5.返回最终结果

在状态转移方程确定后就可以按顺序计算出最终结果了，这里一定要注意状态转移方程执行的顺序，因为这是一个递推的过程，所以必须保证当前方程用到的上一个状态已经得到了。
本题中，执行顺序就是从第1天开始，依次求到最后一天，然后返回从第一天截止到最后一天没有股票的最大利润即可（注意这里最后一天没有股票的最大利润一定是大于有股票的）

完整代码

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    int dp[n][2];
    dp[0][0] = 0, dp[0][1] = -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][0];
}

动态规划总的来说还是需要多做题积累经验，难点就在于如何定义问题的状态，之后就是根据题意确定状态转移方程即可

以上是我对动态规划的理解，下面还有学习了y总的闫氏DP分析法，简单总结了一下，大家也可以参考一下

闫氏DP分析法

将dp问题分成状态表示和状态计算，这里的状态表示就是我们上面说到的状态定义，状态计算就是确定状态转移方程
状态表示化零为整即将一类情况表示为一个集合
状态计算化整为零即将这个集合分解成各个子集，由子集递推出这个集合

01背包问题——题目链接

1.状态表示(化零为整)
f[i][j]->i为考虑前i个物品，j为某种限制，这里是物体体积

集合：所有只考虑前i个物品，且总体积不超过j的选法的集合
属性：最大价值

2.状态计算：(化整为零)
找最后一个不同点，选不选第i个物品，由此可以将状态表示的集合划分为所有不选第i个物品的方案和所有选第i个物品的方案->满足不重复不遗漏

求f[i][j]的最大值只需要分别求选/不选第i个物品的两个集合的最大价值，然后取其中较大的即可。

不选第i个物品的最大值：f[i-1][j]

选择第i个物品的最大值：分成变化和不变的部分，其中不变的部分即一定要选第i个物品价值为wi，变化的部分为前i-1个物品的最大值f[i-1][j-vi],两者相加为f[i-1][j-vi]+wi

Ps:实际情况中还需要特判一下，比如第二种情况当j<vi的时候是不可能包含第i个物品的

#include <bits/stdc++.h>

using namespace std;

const int N = 1001;

int f[N][N];
int W[N];
int V[N];

int main()
{
    int n, v;
    cin >> n >> v;
    for (int i = 1; i <= n; i++)
        cin >> V[i] >> W[i];
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= v; j++)
        {
            f[i][j] = f[i - 1][j];
            if (j >= V[i])
                f[i][j] = max(f[i][j], f[i - 1][j - V[i]] + W[i]);             
        }
    }
    cout << f[n][v];

    return 0;
}

空间优化
f[i][j]=max(f[i-1][j],f[i-1][j-vi]+wi)
计算f[i]时只会用到f[i-1]的数据，可以使用滚动数组来存储结果，进一步第二维只会用j或者j-vi一个比自己小的数，这样只要保证从大到小循环保证f[j-vi]存放的是上一层的f[j-vi]即可简化为下列方程
f[j]=max(f[j],f[j-vi]+wi)

#include <bits/stdc++.h>

using namespace std;

const int N = 1001;

int f[N];
int W[N];
int V[N];

int main()
{
    int n, v;
    cin >> n >> v;
    for (int i = 1; i <= n; i++)
        cin >> V[i] >> W[i];
    for (int i = 1; i <= n; i++)
        for (int j = v; j >= V[i]; j--)
            f[j] = max(f[j], f[j - V[i]] + W[i]);
    cout << f[v];

    return 0;
}

完全背包——题目链接

状态表示
与0/1背包相同
状态计算
完全背包每个物品都有无限多个，集合可以被分成选0/1/2……直到不能选为止

f[i][j]=max(f[i-1][j],f[i-1][j-v]+w,f[i-2][j-2v]+2w,……)
将j替换为j-v
f[i][j-v]=max(f[i-1][j-v],f[i-1][j-2v]+w,f[i-1][j-3v]+2w,……)
结合上述两式可得:f[i][j]=max(f[i-1][j]],f[i][j-v]+w)
Ps:也可从概念上理解，f[i][j]可以表示为不选i的最大值即f[i-1][j]和选了一件i之后继续从前i件物品(包括i)中选择的最大值f[i][j-v]+w

01背包： f[i][j]=max(f[i-1][j],f[i-1][j-v]+w)
完全背包: f[i][j]=max(f[i-1][j],f[i][j-v]+w)
两者只在最后一个f[i-1]/f[i]上有区别，到优化了空间的代码中就是从后往前枚举和从前往后枚举的区别

#include <bits/stdc++.h>

using namespace std;

const int N = 1001;

int f[N][N];
int W[N];
int V[N];

int main()
{
    int n, v;
    cin >> n >> v;
    for (int i = 1; i <= n; i++)
        cin >> V[i] >> W[i];
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= v; j++)
        {
            f[i][j] = f[i - 1][j];
            if (j >= V[i])
                f[i][j] = max(f[i - 1][j], f[i][j - V[i]] + W[i]);
        }
    cout << f[n][v];

    return 0;
}

空间优化

#include <bits/stdc++.h>

using namespace std;

const int N = 1001;

int f[N];
int W[N];
int V[N];

int main()
{
    int n, v;
    cin >> n >> v;
    for (int i = 1; i <= n; i++)
        cin >> V[i] >> W[i];
    for (int i = 1; i <= n; i++)
        for (int j = V[i]; j <= v; j++)
            f[j] = max(f[j], f[j - V[i]] + W[i]);
    cout << f[v];

    return 0;
}

区间DP问题（石子合并）——题目链接

状态表示
f[i][j]：合并i到j堆石子的总代价

集合：所有将[i,j]合并成一堆的方案的集合
属性：代价的最小值

状态计算
集合可以分为[i,i]和[i+1,j]、[i,i+1]和[i+2,j]……共j-i类情况
f[i][j]即为这j-i类情况的最小值

#include <bits/stdc++.h>

using namespace std;

const int N = 310;

int f[N][N];
int s[N];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        s[i] += s[i - 1];
    }
    for (int i = n; i >= 1; i--)
    {
        for (int j = i+1; j <= n; j++)
        {
            f[i][j]=INT_MAX;
            for (int k = i; k < j; k++)
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
        }
    }
    cout << f[1][n];
    return 0;
}