从记忆化搜索到动态规划

 1、要想理解动态规划，首先一定要理解记忆化搜索。

以01背包问题为例：

有 n 个重量和价值为 wi [i] ,v [i] 的物品，从这些物品中挑出重量不超过 t 的物品，求所有选择方案中价值总和的最大值。

首先上的无记忆优化的递归搜索：

#include<bits/stdc++.h>
using namespace std;

const int qq = 1e5 + 10;
const int INF = 1e9 + 10;
const int MOD = 1e9 + 7;

int n,t;
int wi[qq];
int vi[qq];

int rec(int i,int j)    // i,j含义：从第i个物品开始挑选总重小于j的部分
{
    int res;

    if(i == n)          //递归的终结条件，每次一定都会走到i == n
        res = 0;
    else if (j < wi[i]) // 如果发现 j < wi[i] 即背包装不下第i个物品，就向下一个物品 i+1 递归
        res = rec(i+1,j);
    else                // 如果装的下，在此分叉出两种情况：1.不装这个东西，留着空间装价值vi更大的东西 2.装这个东西，背包的容量减小wi[i]
        res = max(rec(i+1,j),rec(i+1,j-wi[i])+vi[i]);

    return res;         // 运行到最后返回 res 让递归的上一层判断
}

int main()
{

    cin >> n >> t;

    for(int i=0;i < n;i++)
        cin >> wi[i] >> vi[i];

    cout << rec(0,t) << endl;

    return 0;
}

在这种情况下，递归的缺点暴露，即大量重复的参数调用，因此我们可以做以下的记忆化搜索优化，只需要修改很小一部分。

#include<bits/stdc++.h>
using namespace std;

const int qq = 1e5 + 10;
const int INF = 1e9 + 10;
const int MOD = 1e9 + 7;

int n,t;
int wi[qq];
int vi[qq];
int dp[qq][qq];

int rec(int i,int j)
{
    if(dp[i][j] >= 0)       //如果发现是已经搜索过的直接返回结果
        return dp[i][j];
    int res;
    if(i == n)
        res = 0;
    else if (j < wi[i])
        res = rec(i+1,j);
        
    else
        res = max(rec(i+1,j),rec(i+1,j-wi[i])+vi[i]);


    return dp[i][j] = res; // 返回 res 的同时令dp[i][j] = res;
}

int main()
{
    memset(dp,-1,sizeof(dp)); //dp初始化

    cin >> n >> t;

    for(int i=0;i < n;i++)
        cin >> wi[i] >> vi[i];

    cout << rec(0,t) << endl;

    return 0;
}

只需要这么一个小小的优化，复杂度缩小到O(NT)

2.从记忆化搜索到动态规划

#include<bits/stdc++.h>
using namespace std;

const int qq = 1e5 + 10;
const int INF = 1e9 + 10;
const int MOD = 1e9 + 7;

int n,t;
int wi[qq];
int vi[qq];
int dp[qq][qq];

int main()
{
    memset(dp,0,sizeof(dp));

    cin >> n >> t;

    for(int i=0;i < n;i++)
        cin >> wi[i] >> vi[i];
    
    for(int i=n-1;i >= 0;i--)   //为什么 i 从 n-1 开始？ 想一想递归都是一直运行到最后才开始计算的。
    {
        for(int j=0;j <= t;j++) // j 从 0 到 t 遍历 ， 但我有个疑惑：记忆化搜索是每次减wi[i]，是不是会比动规 j 遍历的次数少？
        {
            if(wi[i] > j)
                dp[i][j] = dp[i+1][j];
            else
                dp[i][j] = max(dp[i+1][j],dp[i+1][j-wi[i]]+vi[i]);
        }
    }
    
    cout << dp[0][n] << endl;
    
    return 0;
}

这个样子的动态规划是完全按照记忆化搜索演变过来的

3.动态规划的各种变形

很多时候你看到的别人的解法都是很简略、美观的代码，其实这些都是基于熟练掌握的基础上浓缩而成的，基本上是无法从中理解的。

此为正序递推式：

for(int i=0;i < n;i++)
    {
        for(int j=0;i <= t;j++)
        {
            if(j < wi[i])
                dp[i+1][j] = dp[i][j];
            else
                dp[i+1][j] = max(dp[i][j],dp[i][j-wi[i]]+vi[i]);
        }
    }

一维DP

for(int i=0;i < n;i++)
    {
        for(int j=t;j >= wi[i];j--)
        {
            dp[j] = max(dp[j],dp[j-wi[i]]+vi[i]);
        }
    }

动态规划是很抽象的，之前我很总是习惯要搞清楚 dp[i][j] 是怎样在数组中演变过来的，后来觉得思考不过来。只要清楚dp[i][j]是什么意思就好了。