前言
小蒟蒻在某次牛客中奖后，开始学习白嫖的动态规划课程。众所周知，动态规划的学习不是一朝一夕可以完成的，小蒟蒻将持续不定期更新大概率是长期拖更。如果文章中有任何问题，欢迎评论告诉我?。
动态规划的一些概念
动态规划的定义：
动态规划是解决多阶段决策过程最优化问题的一种方法
阶段：
把问题分成几个相互联系的有顺序的几个环节，这些环节即称为阶段。
状态
某一阶段的出发位置称为状态，通常一个阶段包含若干状态。
决策
从某阶段的一个状态演变到下一个阶段某状态的选择。
策略
由开始到终点的全过程中，由每段决策组成的决策序列称为全过程策略，简称策略。
状态转移方程
·前一阶段的终点就是后一阶段的起点，前一阶段的决策选择导出了后一阶段的状态，这种关系描述了由i阶段到i + 1阶段状态的演变规律，称为状态转移方程
·形如：
1.f[i] = f[i - 1] + f[i - 2]
2.f[i][j] = max(f[i - 1][j],f[i - 1][j - 1]) + a[i][j]
动态规划适用的基本条件
具有相同子问题
1.保证问题能分解出几个子问题，并且能通过这些子问题来解决这个问题
2.将这些子问题做为一个新的问题，它也能分解成相同的子问题进行求解。
满足最优子结构
问题的最优解包含它的子问题的最优解。即不管前面的策略如何，此后的决策必须是基于当前状态（由上一次的决策产生）的最优决策
满足"无后效性"
1."过去的步骤只能通过当前状态影响未来的发展，当前的状态是历史的总结"。这条特征说明动态规划只适用与解决当前决策与过去状态无关的问题。状态出现在策略任何一个位置，它的地位相同，都可实施同样策略，这就是无后效性的内涵。
注：
这是动态规划中极为重要的一点，如果当前问题的具体决策会对解决其他未来的问题产生影响，就无法保证决策的最优性
动态规划的一般步骤
1.结合原问题和子问题确定："我"是谁？"我"在哪？
- 题目在求什么？要解决这个问题我们需要知道什么？什么是影响答案的因素？
- 状态的参数一般有：
- 描述位置的：前（后）i单位，第i到第j单位，坐标为（i，j），第i个之前（后）且必须取第i个……
- 描述数量的：取i个，不超过i个，至少i个……
- 描述对后有影响的：状态压缩，一些特殊性质……
2.确定状态转移方程："我"从哪里来？"我"到哪里去？
- 检查参数是否足够（能否将历史描述清楚，不对未来造成影响）
- 分情况：最后一次决策的方式，取不取，怎么样取——前一项是什么
- 初始边界是什么？
- 注意无后效性
- 根据状态枚举最后一次决策（即当前状态怎么来的）就可确定出状态状态转移方程
3.考虑是否需要优化
注：
这里放一个，小蒟蒻之前补题的时候结合一些文章总结的步骤
1.设计状态（定义一个数组，确定其各维含义）
2.状态转移方程（类似于数学归纳法，由前面的状态，根据一定的关系推出后面的状态）
3.找出初始值
一些例子
dh与学妹过桥[这个是之前补题的时候写的分析，直接搬过来叻]
题目内容
吃完饭后dh和学妹一起走到了一条江边，有两列平行的石墩桥，每个石墩上都有一个小写字母，dh对学妹说：我走上面这列石墩，你走下面的石墩，我先走一个石墩然后你在你那列石墩跟着我走一个同样字母的石墩，一直向前走，直到过了这条河，你知道你最多能踩多少个石墩吗？你答的出来吗？
输入格式
输出两行字符串，表示两列石墩桥(字符串长度最大不超过1000)
输出格式:
输出一个整数，表示最多走多少个石墩
输入样例:
abcdef
acebeee
输出样例
3
AC代码
#include <bits/stdc++.h>
using namespace std;
const int N =1e3+5;
#define int long long
char a[N],b[N];
int f[N][N];
signed main()
{
scanf("%s%s",a,b);
for (int i = 0;i < strlen(a); i ++)
for (int j = 0; j < strlen(b); j ++)
{
if (a[i] == b[j]) f[i + 1][j + 1] = f[i][j] + 1;
else f[i + 1][j + 1] = max(f[i][j + 1], f[i + 1][j]);
}
cout << f[strlen(a)][strlen(b)] << endl;
return 0;
}
总结
这题我写错了，后面借助网络的力量，发现理解错题目了。dh走一步，学妹不一定要走到dh站的石墩上的字母上，抽象一下就是典型的dp最长公共子序列（LCS）。
这里也把佬的总结码在这
https://blog.csdn.net/qq_62362934/article/details/125919681
注：佬的总结跟我的有点不一样
解题思路
1.设计状态（定义一个数组，确定其各维含义）
i表示当dh走到a的i位置，j表示学妹走到b的j位置，f[i][j]表示dh走到a的i位置，学妹走到b的j位置时，学妹走的石墩数。其中学妹走过的石墩上的字母，即为a的最长公共子序列，f[i][j]表示最长公共子序列的长度。
2.状态转移方程（类似于数学归纳法，由前面的数据根据一定的关系推出后面的数据）
1)如果有某一个字符串为空的话，f[i][j]=0，在这个是全局变量，初始化为0，不用特别考虑
2)如果a[i]=b[j]，那么dh走一步，学妹也走一步，最长公共子序列的长度可以在原来的基础上+1，表示为：
if(a[i]==b[i]) f[i+1][j+1] = f[i][j - 1] + 1;
3)如果a[i]!=b[j],这时有两种选择，要么dh走一步，要么学妹走一步，又要求最大，那么表示为：
f[i + 1][j + 1] = max(f[i][j + 1], f[i + 1][j]);
3.找出初始值
这里是全局变量，初始化为0。