算法总结—记忆化搜索2

· · 算法·理论

记忆化搜索的本质就是 DP ，是一种快速验证 DP 的算法，今天我们用记忆化搜索来写几道 DP 题。

直接来看一道题： 三倍经验

这道题能用 DP 写，也可以用记忆化搜索写（但我们要用记忆化搜索写）。

状态：

与 DP 一样，表示到第 i 行第 j 列，还剩下 k 次乘 3 机会所获得的数字的最大和。

答案：

状态转移方程：

把状态转移方程右边的 dp 数组全部改为 dfs 函数，就变成了记忆化搜索的状态转移方程，如下:

记忆化搜索: dp[x][y][z]=max(max(dfs(x-1,y,z),dfs(x-1,y-1,z))+a[x][y],max(dfs(x-1,y,z-1),dfs(x-1,y-1,z-1))+a[x][y]*3);

边界条件：

if(x==1&&y==1&&z==0) \ if(x==1&&y==1&&z==1) \ if(x<1||y<1||z<0)

调用答案：

if(vis[x][y][z]==true) return dp[x][y][z];

完整代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[105][105];
bool vis[105][105][5055];
int dp[105][105][5055];
int dfs(int x,int y,int z){
    if(x==1&&y==1&&z==0){
        vis[1][1][0]=1;
        dp[1][1][0]=a[1][1];
        return a[1][1];
    }
    if(x==1&&y==1&&z==1){
        vis[1][1][z]=1;
        dp[1][1][1]=3*a[1][1];
        return 3*a[1][1];
    }
    if(x<1||y<1||z<0){//边界条件
        return -1e18;
    }
    if(vis[x][y][z]==1){
        return dp[x][y][z];
    }
    vis[x][y][z]=1;
    dp[x][y][z]=max(max(dfs(x-1,y,z),dfs(x-1,y-1,z))+a[x][y],max(dfs(x-1,y,z-1),dfs(x-1,y-1,z-1))+a[x][y]*3);
    return dp[x][y][z];
}
signed main(){
    int n,s;
    cin>>n>>s;
    s=min(n,s);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j];
        }
    }
    memset(vis,0,sizeof(vis));//用vis数组储存一个数有没有被算过
    int ans=-3e18;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=s;j++){
            ans=max(ans,dfs(n,i,j));
        }
    }
    cout<<ans;
    return 0;
}

再来看一道题： 过河卒

状态：

dp[x][y] 表示从初始位置到 (x,y) 的路径个数。

答案：

dfs(n,m)

状态转移方程：

记忆化搜索: `dp[x][y]=dfs(x-1,y)+dfs(x,y-1);`

边界条件：

if(x<0||y<0) \ if(vis[x][y]==1)

调用答案：

if(dp[x][y]!=0) return dp[x][y];

完整代码：

#include<bits/stdc++.h>
using namespace std;
long long dp[25][25];
int dx[8]={1,1,2,2,-1,-1,-2,-2};
int dy[8]={2,-2,1,-1,2,-2,1,-1};//八方向
bool tong[25][25];
long long dfs(int x,int y){
    if(x<0||y<0){
        return 0;
    }
    if(tong[x][y]){
        return 0;
    }
    if(dp[x][y]!=0){
        return dp[x][y];
    }
    dp[x][y]=dfs(x-1,y)+dfs(x,y-1);//这是一道求方案数的题，所以不是求max,而是相加
    return dp[x][y];
}
int main(){
    long long n,m,ex,ey;
    cin>>n>>m>>ex>>ey;
    dp[0][0]=1;
    tong[ex][ey]=1;//初始条件
    for(int i=0;i<8;i++){
        int tx=ex+dx[i],ty=ey+dy[i];
        tong[tx][ty]=1;
    }
    cout<<dfs(n,m);
    return 0;
}

最后一道题： 小A点菜

状态：

dp[i][j] 表示从前 i 个菜中选取若干个，放到容量为 j 的背包中，正好装满的方案总数。

答案：

dfs(n,m)

状态转移方程：

`dp[i][j]=dp[i-1][j]` `(j` $ < $ `w[i])`\ 记忆化搜索: `dp[x][y]=dfs(x-1,y)+dfs(x-1,y-w[x])` `(y` $ \ge $ `w[x])`\ `dp[x][y]=dfs(x-1,y)` `(y` $ < $ `w[x])`

边界条件：

if(x==0&&y==0) \ if(x<1||y<0)

调用答案：

if(vis[x][y]==1) return dp[x][y];

完整代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[105];
int dp[105][10005];
bool vis[105][10005];
int dfs(int x,int y){
    if(x==0&&y==0){
        return 1;
    }
    if(x<1||y<0){
        return 0;
    }
    if(vis[x][y]==1){
        return dp[x][y];
    }
    vis[x][y]=1;
    if(y>=a[x]){
        dp[x][y]=dfs(x-1,y)+dfs(x-1,y-a[x]);
    }else{
        dp[x][y]=dfs(x-1,y);
    }
    return dp[x][y];
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    cout<<dfs(n,m);
    return 0;
}

附三题 DP 代码