LeetCode动态规划

动态规划步骤

一般求解最优质：最少，最多




题型主要分为下面的三种：

线性规划问题

一般输入是线性数组，我们利用线性规划

dp[i]依赖前面一个或者两个状态得到

特点：问题的输入是一个数组或者字符串。

dp[i]依赖前面多个状态得到
经典的就是最长递增子序列

dp[i]带有一个或者多个维度

双数组/双字符问题


输入为矩阵的问题

区间动态规划问题

一般求解的是回文串问题
区间动态规划定义二维区间dp[i][j]。这个区间表示的是数组/字符串[i,j]对于的子数组/子串的状态值。

背包问题

动态规划中经典的0-1背包问题

动态规划求解：


压缩空间，将二维压缩成一维，然后填写整个空间，这个过程为了防止后面的状态被前面的状态影响，我们可以采用从后面向前面填写表格的方式。

完全背包问题：


状态转移过程：

思考还有多重背包问题：

还有二维背包问题：

构造树形结构：
需要的下面的树形结构进行剪枝，剪枝策略为递归的索引大于父节点索引，并且值不能小于零。