动态规划
动态规划算法通常用于求解具有某种最优性质的问题。
基本思想：将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
步骤：
1.找出最优解的性质，并刻画其结构特征
2.递归地定义最优值 (写出动态规划方程)
3.以自底向上的方式计算出最优值
4.根据计算最优值时得到的信息，构造一个最优解（自顶向下，递归）
矩阵连乘积问题
已知：给定n个矩阵{A1,A2,…,An}，其中Ai与Ai+1是可乘的，
计算：这n个矩阵的连乘积A1A2…An所需要的乘法运算的次数的最小值.
计算量=A[1:k]的计算量+A[k+1:n]的计算量+A[1:k]和A[k+1:n]相乘的计算量
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e3+5;
const int inf=1e18;
int n;
int dp[N][N],s[N][N],p[N],row[N],col[N];
void dfs(int i,int j)
{
if(i==j)
{
cout<<"A"<<i;return;
}
cout<<"(";
dfs(i,s[i][j]);
dfs(s[i][j]+1,j);
cout<<")";
}
signed main()
{
cin>>n;
for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) dp[i][j]=inf;
for(int i=1;i<=n;i++) dp[i][i]=0;
for(int i=1;i<=n;i++)
cin>>row[i]>>col[i];
for(int i=1;i<=n;i++) p[i]=col[i];
p[0]=row[1];
for(int len=2;len<=n;len++)
{
for(int i=1;i<=n-len+1;i++)
{
int j=i+len-1;
dp[i][j]=dp[i+1][j]+p[i-1]*p[i]*p[j];
s[i][j]=i;
for(int k=i+1;k<j;k++)
{
int tmp=dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j];
if(tmp<dp[i][j])
{
dp[i][j]=tmp;
s[i][j]=k;
}
}
}
}
cout<<dp[1][n]<<endl;
dfs(1,n);
return 0;
}
/*
3
2 3
3 2
2 4
6
50 10
10 40
40 30
30 5
5 20
20 15
*/
备忘录算法：
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e3+5;
const int inf=1e18;
int n;
int dp[N][N],s[N][N],p[N],row[N],col[N];
void print(int i,int j)
{
if(i==j)
{
cout<<"A"<<i;return;
}
cout<<"(";
print(i,s[i][j]);
print(s[i][j]+1,j);
cout<<")";
}
int dfs(int l,int r)
{
if(dp[l][r]!=inf) return dp[l][r];
if(l==r) return 0;
int tmp=dfs(l,l)+dfs(l+1,r)+p[l-1]*p[l]*p[r];
s[l][r]=l;
for(int k=l+1;k<r;k++)
{
int res=dfs(l,k)+dfs(k+1,r)+p[l-1]*p[k]*p[r];
if(res<tmp)
tmp=res,s[l][r]=k;
}
return dp[l][r]=tmp;
}
signed main()
{
cin>>n;
for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) dp[i][j]=inf;
for(int i=1;i<=n;i++) dp[i][i]=0;
for(int i=1;i<=n;i++)
cin>>row[i]>>col[i];
for(int i=1;i<=n;i++) p[i]=col[i];
p[0]=row[1];
cout<<dfs(1,n)<<endl;
print(1,n);
return 0;
}
/*
3
2 3
3 2
2 4
6
50 10
10 40
40 30
30 5
5 20
20 15
*/
动态规划算法的基本要素
最优子结构：问题的最优解包含其子问题的最优解，以自底向上的方法从子问题的最优解逐步构造出整个问题的最优解。
重叠子问题：算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。
备忘录算法与动态规划算法不同的是：
备忘录方法采用的是自顶向下的递归方式，而动态规划算法采用的是自底向上的非递归方式。
最长公共子序列
给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e3+5;
const int inf=1e18;
int n,dp[N][N],s[N][N],len1,len2;
string s1,s2;
void get_lcs()
{
int i=len1,j=len2,k=dp[len1][len2];
string ans="";
while(i>0&&j>0)
{
if(s[i][j]==1)
ans=s1[i]+ans,i--,j--;
else if(s[i][j]==2)
j--;
else
i--;
}
cout<<ans<<endl;
}
signed main()
{
cin>>s1>>s2;
len1=s1.length(),len2=s2.length();
s1=" "+s1,s2=" "+s2;
for(int i=1;i<=len1;i++)
{
for(int j=1;j<=len2;j++)
{
if(s1[i]==s2[j]) dp[i][j]=dp[i-1][j-1]+1,s[i][j]=1;
else
{
if(dp[i-1][j]>dp[i][j-1])
{
dp[i][j]=dp[i-1][j];s[i][j]=2;//上面
}
else
dp[i][j]=dp[i][j-1];s[i][j]=3;
}
}
}
cout<<dp[len1][len2]<<endl;
get_lcs();
return 0;
}
/*
BDCABA
ABCBDAB
*/
最大子段和
动态规划:
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=7e3+5;
const int inf=1e18;
int n,a[N],dp[N];
signed main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],dp[i]=a[i];
int mx=0; //1-i的最大子段和
int ans=0;
for(int i=1;i<=n;i++)
{
if(mx>0) mx+=a[i];
else
mx=a[i];
if(mx>ans)
ans=mx;
}
cout<<ans<<endl;
return 0;
}
/*
BDCABA
ABCBDAB
*/
记录起始和终止位置：
const int N=7e3+5;
const int inf=1e18;
int n,a[N],dp[N];
signed main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],dp[i]=a[i];
int mx=0; //1-i的最大子段和
int st=0,ed=0,ans=0,tmp=0;
for(int i=1;i<=n;i++)
{
if(mx>0) mx+=a[i];
else
mx=a[i],tmp=i;
if(mx>ans)
{
ans=mx;st=tmp,ed=i;
}
}
cout<<st<<" "<<ed<<endl;
cout<<ans<<endl;
return 0;
}
/*
6
-2 11 -4 13 -5 -2
*/
分治:
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=7e3+5;
const int inf=1e18;
int n,a[N];
int dfs(int l,int r)
{
int sum=0;
if(l==r)
sum=a[l]>0?a[l]:0;
else
{
int mid=l+r>>1;
int ls=dfs(l,mid);
int rs=dfs(mid+1,r);
int s1=0,left=0;
for(int i=mid;i>=l;i--)
{
left+=a[i];
if(left>s1) s1=left;
}
int s2=0,right=0;
for(int i=mid+1;i<=r;i++)
{
right+=a[i];
if(right>s2) s2=right;
}
sum=s1+s2;
if(sum<ls) sum=ls;
if(sum<rs) sum=rs;
}
return sum;
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
cout<<dfs(1,n)<<endl;
return 0;
}
/*
6
-2 11 -4 13 -5 -2
*/
0-1背包问题
int n,m,f[105][N],dp[N];
void fun1()
{
for(int i=1;i<=n;i++) //物品i
{
for(int j=1;j<=m;j++) //容量j
{
if(j<w[i])
f[i][j]=f[i-1][j];
else
f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]);
}
}
cout<<f[n][m]<<endl;
}
void fun2() //逆序更新
{
for(int i=1;i<=n;i++)
{
for(int j=m;j>=w[i];j--)
dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
}
}
最长单调递增子序列
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=7e3+5;
const int inf=1e18;
int m,n,a[N],dp[N];
signed main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],dp[i]=1;
for(int i=2;i<=n;i++)
{
for(int j=1;j<i;j++)
{
if(a[j]<=a[i])
dp[i]=max(dp[i],dp[j]+1);
}
}
cout<<dp[n]<<endl;
return 0;
}
/*
8
65 158 170 155 239 300 207 389
*/
const int N=7e3+5;
const int inf=1e18;
int m,n,a[N],dp[N];
signed main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],dp[i]=1;
int ans=0;
for(int i=2;i<=n;i++)
{
int k=0;
for(int j=1;j<i;j++)
{
if(a[j]<=a[i]&&k<dp[j])
k=dp[j];
}
dp[i]=k+1;
if(ans<dp[i]) ans=dp[i];
}
cout<<ans<<endl;
return 0;
}
/*
8
65 158 170 155 239 300 207 389
*/
数字三角形问题
(过于简单)
FatMouse and Cheese
备忘录做法 （可以去研究，先放过）
![线程同步，可重入锁，synchronized[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)