练习使用markdown（一）（bushi

对dp的一些理解

dp 类问题的解决方法
个人听到一般有两种叫法 一个是动态规划 另一个则是状态转移

算法中的dp个人更倾向于第二种叫法 原因如下

dp处理问题的方式 简单来说就是不断更新已知信息（或者叫状态）并用其帮助进行下一步的决策

此处可以联想一下kmp算法——
kmp算法是进行优化是先获取了模板串的重复字符以类似树的方式存储下来 每次不匹配时就可以回溯尝试别的匹配形式 。
而且由于模板串是不变的所以可以提前处理出已知信息并存储方便进行优化。

    for (int i = 2, j = 0; i <= n; i++)
    {
        while (j && p[i] != p[j + 1])
            j = ne[j];
        if (p[i] == p[j + 1])
            j++;
        ne[i] = j;
    }

而dp类问题要使用的状态是变动的，所以要转移
每个f[i][j]/f[i]的重新赋值都是在对新的状态的存储。
因此个人感觉称其为状态转移更易理解

当然叫什么其实也并不重要 重要的是明白解决此类问题思路就是##状态转移##这一核心思想

解决方法

1.首先明确此问题是否需要用dp解决（暴搜 dfs能过要什么dp[doge]) 多层问题一般需要dp

多层问题也可能使用分治的思想注意区分 可通过分析最优子结构处理方法来分析
dfs bfs有思路但 tle dp

2.构思好状态转移方程（抄板子bushi

状态转移方程思考方法可以从单个状态分析 单个状态的如何转移可得出普遍规律（就是yxc说的从最后开始分析）

3.确定存储状态的数据类型

判断方法 根据最后需要的结果的形式来判断 大部分都是二维形式
如区间用两个坐标表示左右边界 状压dp 和 一些简单的状态机 （？）
用其中一位表示状态（其中有些可以用记忆化搜索代替的可以直接用函数参数表示）
两个坐标的前后位置可以通过最外层遍历的是谁来确定 可参见最短编辑距离
此处有很多技巧 如二维数组的巧妙使用——不考虑其空间之间的关系 只关心表面上的i j
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
背包的一维优化 覆盖掉使用过的现在没有用的信息 注意要通过下一层需要使用的顺序来决定覆盖顺序
for(int j = m; j >= v; j--) f[j] = max(f[j], f[j - v] + w);
二维数组可以用其中一位表示状态 （此类思路即为用空间换时间 可以类比应用到其他部分）
待补充···

4.预处理 先处理好边界、前缀和等转移时会遇到的问题!!!容易忘记 |memset 特殊点赋值（尤其是memset后）

总结？ : dp真难学：< 遇到相似的我才会写 不说了上号打游戏

参考文献 ： 暂无 如有雷同 纯属荣幸。

以上来自一个总时长不到半年 实际学习算法时间不超过半个月的真蒟蒻的一点不成熟的想法同时练习使用markdown 不会调图片大小 对dp的学习仅限于算法基础课（甚至还没学完） 如有想法请您不吝赐教

////////////////更新 2022.3.15/////////////
基础课的dp学完了

菜菜 求求 大佬 带带

完