无后效性
动态规划是一种解决问题的方法,主要用于求解具有一定重叠子问题和最优子结构性质的问题。它将一个复杂的问题分解为更小的子问题,以避免重复工作。以下是动态规划的一些经典思路:
确定状态:在动态规划中,状态通常是一个或多个变量的组合,这些变量能够完全描述当前的问题。比如在背包问题中,状态可以是”当前考虑到的物品”和”当前背包的容量”。
确定状态转移方程:状态转移方程描述了如何从一个状态转移到另一个状态。比如在背包问题中,状态转移方程可能是”如果当前物品的重量小于等于背包的当前容量,那么可以选择放入或不放入背包,取两者价值最大的作为当前状态的值。”
确定边界条件:边界条件描述了最简单的、无法再分解的子问题的解。比如在背包问题中,边界条件可能是”当没有物品或背包的容量为0时,背包中的物品价值为0。”
计算顺序:通常我们会从边界条件出发,按照一定的顺序逐步计算出所有的状态。比如在背包问题中,我们可能会先计算出所有只考虑第一个物品时的状态,然后计算出所有只考虑前两个物品时的状态,以此类推,直到计算出所有考虑所有物品时的状态。
储存结果:通常我们会用一个数组或者其他数据结构来保存所有的状态,以便在计算一个状态时可以快速地查找到相关的状态。
dp思路f1[n][m]是(1,1)到(n,m)的最大值,,,起点开始走
f2[x][x]是(n,m)到(1,1)的最大值,,,结束点开始走,,两边双向维护
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
#define int long long
int n,m;
int f1[2010][2010];//1 1 到
int f2[2010][2010];
int a[2010][2010];
pair<int,int> b[100];
void solve()
{
int t; cin>>t;
vector<int>x(t+1),y(t+1);
for(int i=1;i<=t;i++)
{
cin>>x[i]>>y[i];
}
int ans=f1[n][m];
for(int i=1;i<=t;i++)
{
for(int j=1;j<=t;j++)
{ if(i==j) continue;
ans=max(f1[x[i]][y[i]]+f2[x[j]][y[j]],ans);
}
}
cout<<ans<<endl;;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
memset(f1,-0x3f,sizeof(f1));
memset(f2,-0x3f,sizeof(f2));
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
f1[1][0]=f1[0][1]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
f1[i][j]=max(f1[i-1][j]+a[i][j],f1[i][j-1]+a[i][j]);
}
f2[n+1][m]=f2[n][m+1]=0;
for(int i=n;i>=1;i--)
for(int j=m;j>=1;j--)
{
f2[i][j]=max(f2[i+1][j]+a[i][j],f2[i][j+1]+a[i][j]);
}
int T; cin>>T;
while(T--)
solve();
return 0;
}
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
using namespace std;
int n;
int dp1[5001],dp2[5001]; //此处用两个滚动数组记录,一个记录之前的状态,一个记录此时的状态
char str1[5001],str2[5001];
int main()
{
//freopen("palindrome.in", "r", stdin);
//freopen("palindrome.out", "w", stdout);
scanf("%s", str1+1);
n = strlen(str1+1);
for(int i = 1; i <= n; i++)
str2[i] = str1[n-i+1]; //做一个逆序的字符串数组
for(int i = 1; i<=n; i++)
{
for(int j = 1; j <= n; j++)
{ if(str1[i] == str2[j])
dp1[j] = dp2[j-1]+1; //“发现”匹配就记录
else
dp1[j] = max(dp1[j-1],dp2[j]);
} //不匹配就匹配后面的状态
memcpy(dp2, dp1, sizeof(dp1)); //记录之前的状态“滚动”匹配
}
printf("%d\n", n-dp1[n]); //字符串长度减去匹配出的最长公共自序列的值
return 0; //即需要添加的字符数
}
#include<bits/stdc++.h>
using namespace std;
int dp[310][310],len,a[310],n,sum[310];
int main()
{
cin>>n;
memset(dp,0x3f,sizeof(dp));//初始化1,因为是求最小代价,所以初始化设为很大的一个数,为了后面更新。
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=sum[i-1]+a[i];
dp[i][i]=0;//初始化2,他自己本身的代价为0。
}
for(int len=2;len<=n;len++)
{
for(int i=1;i<=n-len+1;i++)//左端点
{
int j=i+len-1;//右端点
for(int k=i;k<j;k++)//中间点
{
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
}
}
}
cout<<dp[1][n];
}