Q:dp就是记忆化搜索吗？

A:

DP（动态规划）和记忆化搜索有一定的联系，但它们并不完全相同。

相同点

• 核心思想一致：它们都利用了“相同参>数答案相同的特性”，通过记录已计算的结果>来避免重复计算，从而优化时间复杂度。
• 可以相互转换：在很多情况下，记忆化搜索可以转化为动态规划，反之亦然。

不同点

• 实现方式：
  • 动态规划：通常是自底向上的迭代方式，通过填表的方式逐步求解。
  • 记忆化搜索：基于递归实现，通过在搜索过程中记录已计算的结果来避免重复计算。
• 适用场景：
  • 动态规划：适用于具有重叠子问题和最优子结构特性的问题，且通常需要明确的状态转移方程。
  • 记忆化搜索：适用于递归搜索过程中存在大量重复计算的情况，尤其在问题的递归结构较为复杂时更为方便。
• 效率：在某些情况下，记忆化搜索可能比动态规划更高效，因为它只计算“有价值的点”，而动态规划可能会计算一些不必要的状态。

总结

记忆化搜索可以看作是动态规划的一种实现方式，但它们在实现方式、适用场景和效率上有所不同。不能简单地说DP就是记忆化搜索，但它们在很多情况下是相通的。

Note

分组背包: f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i]);

//分组背包
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010;
int f[N][N]; //状态定义数组 初始值因为全局都是0了
int v[N], w[N]; //用来接收每个物品的体积和价值

int n, m, a, b; //表示物品个数 背包体积 a是物品i的体积 b是价值

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        cin >> v[i] >> w[i];
    }
    /*
        01背包的二维状态转移方程
        不选 f[i][j] = f[i-1][j];
        选(在体积够的情况下) f[i][j] = f[i-1][j-v[i]] + w[i];
        f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i])
    */
    //物品从1开始 0个物品价值为0
    for(int i = 1; i <= n; ++i)
        //因为要保证背包容量是大于物品i的体积 所以体积直接从物品容量开始枚举
        for(int j = 0; j <= m; ++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][m] << endl;
    system("pause");
    return 0;
}

区间DP

区间dp：就是对于区间的一种动态规划，对于某个区间，它的合并方式可能有很多种，我们需要去枚举所有的方式，通常是去枚举区间的分割点，找到最优的方式(一般是找最少消耗)。

例如：对于区间【i，j】，它的合并方式有很多种，可以是【i，i+1】和【i+2，j】也可以是【i，k】和【k+1，j】（其中i <= k < j）……