[算法] 动态规划

作者: 舒也ella | 来源:发表于2019-01-15 23:34 被阅读13次

4. 动态规划算法
Swift 算法实战：动态规划
程序员算法基础——动态规划
动态规划
动态规划 Dynamic Programming
动态规划-js
动态规划
2018-11-14
动态规划
最短路径解决方法

两大条件：

重复子问题
判断：同一问题的各个子问题是独立的，彼此不共享资源；但不同问题的子问题是重叠的
带备忘录的递归方法
使用一个数组记录先判断数组是否已计算过
最优子结构
判断：反证法，假设子问题的解不是最优解那么通过cut子问题paste最优解一定可以得出原问题一个更好的解从而退出矛盾

四步求解：

分析最优解的结构
递归定义最优解的值
（最优解通常需要做出选择，思考时要假设选择中用到的子问题已经被解决）
自底向上计算最优解的值
判断二维(一维)数组求解方向
自顶向下递归构造最优解

时间复杂度为：子问题的总个数 * 每个子问题有多少种选择，空间复杂度即子问题的个数
根据子问题的数目 $O(n^t)$ 和每个子问题依赖其他子问题的个数 $O(n^e)$ 可以划分四类tD/eD方程：

1D/1D
已知D[0]，状态转移方程为 $E[j] = min_{0 \leq i < j}{\{D[i] + w(i,j)\}}$
LIS最长递增总序列
钢条切割
整齐打印
最大连续子数组和/乘积
2D/0D
已知D[i,0]和D[0,j]，状态转移方程为 $E[i,j] = min{\{D[i-1,j]+x_i, D[i,j-1]+y_j, D[i-1, j-1]+z_{i,j}\}}$
LCS最长公共子序列
最长回文子序列
字符串编辑距离
二维矩阵最优路径
2D/1D
已知D[i,i]=0，状态转移方程为 $E[i,j] =w(i,j) + min_{i < k \leq j}{\{D[i,k-1]+D[k,j]\}}$
BST最优二叉搜索树
矩阵链乘
2D/2D
已知D[i,0]和D[0,j]，状态转移方程为 $E[i,j] = min_{0 \leq i' < i, 0 \leq j' < j}{\{D[i',j'] + w(i'+j',i+j)\}}$
上述方程中的D[i,j]都可根据E[i,j]在常数时间内算出来

常见的DP类型

数位DP

数位DP通常用于解决两个整数a，b之间存在多少满足某个条件的数（且条件与数字每一位有关）的问题。
假设给定数x，包含n位，表示为 $t_nt_{n-1}...t_1$ ，那么当我们求解n位数字 $t_nt_{n-1}...t_1$ 的状态所对应的答案时就需重复计算n-1位数字 $t_{n-1}t_{n-2}...t_1$ 的状态所对应的答案，因此具有重复子问题。
考虑DP状态为dp(idx, tight, sum)