五大常用算法 - 动态规划

动态规划

1. 动态规划概念

动态规划与分治法形似，都是通过组合子问题的解来去接原问题。分治法，将问题划分为互不相交的子问题，递归地求解子问题，再将它们的解组合起来，求出原问题的解。动态规划，应用于子问题重叠的情况，即不同子问题具有公共的子子问题。在子问题重叠的情况下，分治法会反复求解那些公共子子问题，而动态规划对每个子问题只求解一次，将解保存在一个表格中，从而无需反复求解公共子子问题。所以动态规划问题中，子问题间往往不是独立的，即下一子阶段的解是建立在上一子阶段的解的基础上，进一步求解的，反复递推得到最终解；分治法问题中，子问题间相互独立，子问题之间的解相互独立，最终解由个子阶段的解合并而成。

动态规划常用来求解最优化问题。

2. 动态规划步骤

动态规划，是一个包含多个子阶段的状态的状态链。从初始状态开始，经过中间决策序列中的状态转移，达到最终状态。决策过程如下图所示：

(1) 动态规划问题求解步骤

划分问题阶段：根据时间或者空间顺序将问题划分成有序的问题阶段，并且确定初始阶段
抽象出状态变量：找到各子阶段状态的共同特征，得到状态变量的抽象表达
明确决策和状态转移：决策是状态转移的触发点，决策用来过滤本阶段的可行解或者最优解，从而进行状态转移。
终止条件：动态规划是一个决策链，终止条件定义了递推过程的终止点。

(2) 算法通用实现

动态规划算法有两种实现方式，递归和迭代。用递归实现，因为公共子问题的解是保存在表格中的，所以即便使用了递归，也不会出现重复公共子问题计算。

dp[row-1][col-1] 二维数组存储状态变量
dp[0][0]=XXX // 确定初始状态
for(int i=1; i<row; i++)
	dp[i][0]=dp[i-1][0]+option // 决策+状态转移方程---->递推首列
for(int j=1; j<coll j++)
	dp[0][j]=dp[0][j-1]+option // 决策+状态转移方程---->递推首行
for(int i=1; i<row; i++)
	for(int j=1; j<col; j++)
		dp[i][j]=dp[i][j-1]/dp[i-1][j]+option // 决策+状态转移方程---->递推中间状态
		
return dp[row-1][col-1](最终状态)/或者状态转移过程

3. 动态规划适用条件

分治法应用的问题具有如下性质：

(1) 最优子结构性质，即问题的最优解，包含了其中子结构的最优解。

(2) 重叠子问题性质，下一子阶段的解是建立在上一阶段子问题解的基础上，递推得出的。则之前子子问题是反复包含于后续子问题中的。

(3) 后无效性质，某状态的转移，只与当前状态有关，与其后决策的影响。

4. 常见问题

《LeetCode》相关问题