dynamic programming

动态规划总结

题型概述：

动态规划可以理解为一个有限状态机，根据之前的状态推出现在的状态，针对之前已经出现过的状态可以采取一些去重方式减少计算量，但是本质是递归。

五部曲：

1.确定dp数组的含义 一般dp数组的含义直接和需要的返回值直接有关。

2.确定递推公式

3.初始化dp数组

4.确定遍历顺序 遍历顺序和逻辑顺序有关，也会影响输出结果。

5.手推模拟过程

一些经典题型：

路径条数：一般dp数组设置为i，j位置到达的条数

根据目标移动的逻辑设置地推函数

01背包：往往能抽象为两个子集的最小和。

只能用一次，因此从大开始遍历

组合类背包：dp[j] +=dp [j-nums[i]]

完全背包：

可使用的物品数目不限制，其相对于01背包有以下特点： 1.遍历顺序无关，由于不限制只能用一次，因此可以从小开始遍历 2.组合：顺序无关，先遍历物品 排列：顺序有关，先遍历背包。

爬楼梯的在思考：

可以抽象为一个完全背包问题，即每次可以放入1或者2，问放满n的最多放法 注意这是一个排列问题，即1，2和2，1是不一样的。

多重背包：

背包内物体有数量限制

打家劫舍

两种思路：dp数组的含义： 1.第i个一定偷的最大，但是在dp循环后还要找个最大值 2.第i个是目前能偷到的最大值

树形dp

递归遍历，dp数组的含义是该节点偷/不偷的最大值，后序遍历递归向上到根节点。

买卖股票：

此类问题的的关键是思考每天究竟有几种状态，最一般的情况是两种（是否持有股票） k次持有：2*k+1个持有与否的状态 冷却期：四个状态

dp[i][0]:第i天不持有股票的最大余额 dp[i][1]:第i天持有股票的最大余额

序列类：

考虑算法的要求，一般是前i位置的子序列的符合要求。

子数组/子序列类：

1.可以删除中间的(公共）： 2.不可以删除中间的（连续）： 两类的主要区别在于迭代公式，如果是公共的，可以继承之间算出的最长序列 如果是连续的，如果碰到不同的则需要重新计数

删除类

比较两个字符串，需要二维dp数组，往往含义是i-1位置结尾和j-1位置结尾的字符串的符合要求的个数/长度。 递推公式：看其能继承的方向，一般是左上，左，上，三个方向，根据目前遍历位置的是否相同决定使用哪一个。

编辑距离类：

编辑距离类是三种操作：增加，删除，修改，得到两个字符串相同的最小步数 dp数组含义：最小的操作数 地推公式： 假设两个最后字符相同：不需要操作，和之前相同 不同： 1.需要删除字符串a：dp[i-1][j]+1; 2.需要删除字符串b：dp[i][j-1]+1; 3.需要添加字符串a（等于删除b）：dp[i][j-1]+1; 4.需要添加字符串b（等于删除a）：dp[i-1][j]+1; 5.需要修改字符，修改这个字符后等于用一次操作使得两个字符串相同，即dp[i-1][j-1]+1

回文子串系列

看i和j位置的字符一不一样，再看i+1和j-1的字符串是不是回文的。 注：子串和子序列的不同：能不能继承

Build with Jekyll and true minimal theme