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

以01背包问题为例：

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

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

#include
     
      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
     
      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
     
      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]是什么意思就好了。