1.动态规划的基本原理

动态规划通过把一个大问题分解成若干小问题解决，而当前状态是由上个子问题通过状态转移得到结果的，最终通过返回值得出问题的最优解。

2.简单动态规划

我们已经知道了dp的原理，但究竟该怎么编写代码呢，请看下面的例题。

分析：数字三角形只能往下或右下，所以当前节点最大为max(f[i-1][j-1],f[i][j-1])+a[i];

所以，我们得到了状态转移式：f[i][j]=max(f[i-1][j-1],f[i][j-1])+a[i]; 而这就是动规的核心。

代码如下：

#include<iostream>
using namespace std;
const int N=1010;
int a[N][N],dp[N][N];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++) cin>>a[i][j];
	dp[1][1]=a[1][1];
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++) dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j];
    }
    int ans=0;
    for(int i=1;i<=n;i++) ans=max(ans,dp[n][i]);
    cout<<ans;
    return 0;
}

3.动态规划的提高

刚才我们已经初步了解了dp，下面来做一道稍微提高了一点难度的题。

分析：若点(i,j)的上下左右存在点(i1,j1),则f[i][j]=max(f[i][j],f[i1][j1]+1);

代码：

//本题采用记忆化搜索+dp
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m,ans;
int a[N][N],f[N][N];
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
int solve(int x,int y)
{
    if(x<1||x>n||y<1||y>m) return 0;
    if(f[x][y]) return f[x][y];
    f[x][y]=1;
    for(int i=0;i<4;i++){
        int u=dx[i]+x,v=dy[i]+y;
        if(a[x][y]>a[u][v]){
            f[x][y]=max(f[x][y],solve(u,v)+1);
        }
    }
    return f[x][y];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) cin>>a[i][j];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) ans=max(ans,solve(i,j));
    }
    cout<<ans;
    return 0;
}

本文就聊到这，感谢大家的收看~~~