常规入门DP解题思考方向及解题步骤

常规入门DP解题思考方向及解题步骤

引用

CSDN

1.

https://m.blog.csdn.net/2402_87686098/article/details/145947252

动态规划（DP）是算法学习中的一个重难点，初学者往往容易被劝退。但是，如果找到合适的学习方法，常规DP并不是无迹可寻，入门也并不难。本文将通过对比DFS、记忆化搜索和DP的解题思路，以及具体的解题步骤，帮助读者理解DP算法的核心思想。

思考方向

DFS -> 记忆化搜索 -> （递推）DP

总括：学过DFS的应该都画过树形图，DFS就是从树头的一个问题逐渐往下延伸，递归遍历到数的每个节点，考虑到每一种遍历情况，最后取得最优解的一种算法；记忆化搜索，便是在DFS的基础上，记录已遍历过的情况，防止重复多次遍历的优化方法；而递推便是在掌握DFS的基础上进一步优化问题的算法，由树的根节点不断往上推，最终推出问题的答案（将一个问题不断划分成多个子问题，并保存下来每个子问题的答案，由一个个子问题不断推出总问题的答案）。

光说很难理解，下面我将以洛谷一道题来实际展示一遍

https://www.luogu.com.cn/problem/P1216

DFS（数据范围较大肯定过不了）

写DFS之前先画一下递归搜索树（本题题目直接给了。。。）

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int g[N][N];
int n;
int dfs(int xx,int yy)
{
    if(xx>n||yy>n)return 0;
    else return max(dfs(xx+1,yy),dfs(xx+1,yy+1))+g[xx][yy];//选左下或右下
}
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)//一共n行
    {
        for(int j=1;j<=i;j++)//第i行有i个数
        {
            cin >> g[i][j];//读入
        }
    }
    int res=dfs(1,1);
    cout <<res;
}  

需要注意的是

max(dfs(xx+1,yy),dfs(xx+1,yy+1))+g[xx][yy]；

本行的两个DFS分别对应的是取左下或右下的两种情况所对应的子问题的最大值，而非左下或右下两个数的最大值，如此一直递归下去，每个子问题都是最优的，最后所得答案也是最优的；

记忆化搜索（本题记忆化搜索效果不是太明显，洛谷上有一个测试点过不去）

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int g[N][N];
int n;
int m[N][N];
int dfs(int xx,int yy)
{
    if(m[xx][yy])return m[xx][yy];//如果当前节点之前遍历过，边可以直接return，不用在重复无用功
    int sum=0;
    if(xx>n||yy>n)return 0;
    else sum=max(dfs(xx+1,yy),dfs(xx+1,yy+1))+g[xx][yy];
    return m[xx][yy]=sum;
}
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            cin >> g[i][j];
        }
    }
    int res=dfs(1,1);
    cout <<res;
}  

记忆化搜索没什么可说的，直接套模版即可，模版如下：

{
    if(mm[][])return mm[][];
    int sum=0;
    sum=dfs(,);
    mm[][]=sum;
    return sum;//这行和上面那一行和简写成return m[][]=sum;一行
    //原因是赋值运算优先于return
}  

DP（递推）

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int g[N][N];
int n;
int m[N][N];
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            cin >> g[i][j];
        }
    }
    for(int i=n;i>=1;i--)
    {
        for(int j=i;j>=1;j--)
        {
  //max(dfs(xx+1,yy),dfs(xx+1,yy+1))+g[xx][yy];对比发现一模一样
    m[i][j]=max(m[i+1][j],m[i+1][j+1])+g[i][j];
        }
    }
    cout <<m[1][1];
}  

由此可以发现，只要写出来DFS那么递推就手到擒来

解题步骤

说完了DP的思考方向，接下来给出一个思考该类问题的一个具体步骤

1. 重述问题
2. 找到问题最后一步
3. 去掉问题最后一步，新问题变成了什么（子问题）
4. 考虑边界

依旧是以具体题目为例（这个我以力扣当中的一个题举例说明具体如何操作）

https://leetcode.cn/problems/integer-break/description/

1. 重述问题：将一个数n拆成k个数，并使这k个数的乘积最大化
2. 最后一步：找到所拆的数中的最后一个数（也就是最大的一个数），在这我们把这个数记成c
3. 去掉最后一步的新问题：将（n-c）拆成k-1个数，并使这（k-1）个数乘积最大化
4. 边界：不断重复2,3两步，最终变成将0/1拆成0个数，并使这0个数乘积最大化，也就是f[0]=f[1]=1;(0和1都不可再拆)

const int N=60;
class Solution {
public:
int f[N];
int dfs(int x)
{
    int res=0;
    if(x==0)return 0;
    if(f[x])return f[x];
    for(int i=1;i<x;i++)
    {
        res=max(res,max((x-i)*i,dfs(x-i)*i));
    }
    return f[x]=res;
}
    int integerBreak(int n) {
        return dfs(n);
    }
    
};  

省去的DFS直接给出了记忆化搜索代码

然后再将这个代码改写成递推形式

const int N=60;
class Solution {
public:
int f[N];
    int integerBreak(int n) {
        f[1]=f[0]=1;
        for(int i=1;i<=n;i++)
        for(int j=0;j<i;j++)
        {
            f[i]=max(f[i],max(j*(i-j),j*f[i-j]));
        }
        return f[n];
    }
    
};  

第一次写博客，有很多地方不够完善，也可能有错误，希望大家看到错误告诉我，一起进步~~~