DP梳理

DP，动态规划

DP和记忆化搜索本质上是一个东西，zhn说矛盾只是考虑同一种问题的两种不同方法

数学中一共有三个主要矛盾：代数和几何，统计和因果，连续和离散 (Zhu, 2025)

动态规划有两个特性：

1.重叠子问题，换言之对于不同的大问题，小问题会被重复计算

2.最优子结构，换言之组成大问题最优解的每一个小问题答案都是小问题的最优解

对于重复计算的问题，最直白的想法就是，计算出最优解之后就把这个最优解存起来，这样以后随时可以用

对于问题和问题之间的推导，就需要建立答案和答案之间的联系，这就是所谓的状态转移方程

如果你可以得出从一些既有答案得出一些未来的答案的关系，那你就得到了状态转移方程

DP和记忆化搜索都有类似的状态转移方程

不同的是，在记忆化搜索中我们是从顶端开始，向下寻找一切问题的根源，而后得到一些确定的根源后再一层层把问题返回回去，它是自顶向下的

而DP，它需要一系列的基础情况，根据这些基础情况，一步步往前推导迭代，最后抵达那个需要的位置，它是自底向上的

在这个过程中就能看出来，DP会计算许多对于解答答案并不重要的数据，或者说所谓“光锥”之外的东西，而记忆化搜索永远局限于“光锥”之内

举个例子，求斐波那契数列的第n项，记忆化搜索会如此实现：

CPP

int mapp[10005];
int search(int n){
    if(n==1 || n==2)return 1;
    if(!mapp[n])mapp[n] = search(n-1)+search(n-2);
    return mapp[n];
}

而DP就会这样：

CPP

int mapp[10005];
int dp(int n){
    mapp[1] = 1;
    mapp[2] = 1;
    for(int i=3;i<=n;i++){
        mapp[i] = mapp[i-1]+mapp[i-2];
    }
    return mapp[n];
}

我个人在依靠这种思维方式思考问题的时候遇到了阻碍，所以我考虑了另一种构建问题的方法，中二一点说的话，就是：

我从当下我能去往何方？

CPP

int mapp[10005];
int dp(int n){
    mapp[1] = 1;
    for(int i=1;i<=n;i++){
        mapp[i+1]+=mapp[i];
        mapp[i+2]+=mapp[i];
    }
    return mapp[n];
}

也就是直接利用已经解决的子问题向上推导，发散到能够触碰到的位置，有点类似BFS，这个方法和经典的DP思路是等价的，只不过这个方法会略微浪费一点空间

DP这玩意的灵活性堪比二分，而且由于构建“变化”也即状态转移方程的过程往往很折腾，所以难度上是要高于二分答案的

所以说这玩意恶心嘛啧

（待续）

文章操作

相关推荐

评论

DP梳理