动态规划
动态规划，动规，DP
判断
- 看到最大值、最小值
- 看到有几种可能性
分类
1.迷宫问题
- 走到一个点有几种走法
- 走到一个点获得的最大值
dp[i][j]=所有能走到此点的（路径或最大值）和
e.g. dp[i][j]=dp[i-1][j]+dp[i][j-1]
或 dp[i][j]=max(dp[i-1][j]+dp[i][j-1])+a[i][j]
注意：高精度
- 当迷宫大小超出60时
- 当迷宫中取数数的大小较大时
高精度实现：
dp开三维，dp[i][j][0]存位数，dp[i][j][k]存第k位，最后逆序输出
加法
int len=max(dp[i-1][j][0], dp[i][j-1][0]);
for(int k=1; k<=len; k++)
{
dp[i][j][k]+=dp[i-1][j][k]+dp[i][j-1][k];
dp[i][j][k+1]+=dp[i][j][k]/10;
dp[i][j][k]%=10;
}
if(dp[i][j][len+1]!=0) len++;
dp[i][j][0]=len;
乘法
int len=dp[i-1][j][0]+dp[i][j-1][0]-1;
for(int p=1; p<=dp[i-1][j][0]; p++)
{
for(int q=1; q<=dp[i][j-1][0]; q++)
{
dp[i][j][p+q-1]=dp[i-1][j][p]*dp[i][j-1][q];
dp[i][j][p+q]=dp[i][j][p+q-1]/10;
dp[i][j][p+q-1]%=10;
}
}
if(dp[i][j][len+1]!=0) len++;
dp[i][j][0]=len;
当然你要重载运算符也不拦着你
⚠️十年OI一场空，不开long long见祖宗
2.背包问题
- 0-1（1个物品1件）
- 完全（1个物品无数件）
- 多重（1个物品多件）
确定背包属性：看一个物品有几个属性 -> 几个属性就是几维
特别的题目：公司物品分配
dp[i][j]=考虑到第i个公司，已经分了j台机器的最大利润
switch(backpack){
case "一维背包":
/*初始化*/
dp[0]=1;
/*for循环*/
dp[i]=1/*(或0)*/
//表示i这个状态能否达到;
break;
case "二维背包":
/*初始化*/
memset(dp,-1,sizeof(dp));
dp[0]=0;
/*for循环*/
dp[i]=i这个状态所获得的最值/*打擂台*/;
break;
}
for(枚举物品种类)
for(依次枚举数组下标/*0-1和多重：从后往前，完全：从前往后*/)
/*for(多重：枚举物品数量)*/
if(这个状态能达到 && 下标不越界){
打擂台求最值;//也就是状态转移方程，注意-1
//e.g. dp[j+a[i]]=max(dp[j]+b[i], dp[j+a[i]];
}
}
}
3.区间DP
根据断点分左右
例题：乘积最大
dp[i][j]表示i起点，j终点，能降维降维（取消起点）
for(枚举分支长度){
for(枚举起点){
手动算终点；//终点=起点+长度-1;
if(终点越界) break;
for(枚举断点/*在起点和终点之间*/){
根据规则计算dp[i][j];
//依据断点分成左右，写出状态转移
}
}
}
cout<<dp[1][n];
4.其它问题
最长上升/下降/不上升/不下降子序列 （最好用单调栈做）
下面是动规解法：
for(int i=1; i<=n; i++)
for(int j=1; j<i; j++)
if(a[j] < /*这里可能要换符号*/ a[i]){
dp[i]=max(dp[i],dp[j]+1);//找出最长的一段，把“我”接在后面
}
}
}
题单
洛谷上的题单（来自于其他用户）：dp题单