算法之回溯&动态规划&贪心

回溯使用场景：求出所有可能的解。

List result;
void backtrack(路径,选择列表){
	if(满足结束条件){
		result.add(路径);
		return;
	}
	for(选择:选择列表){// 遍历集合中的元素
		做选择;
		backtrack(路径,选择列表);
		撤销选择;
	}
}

动态规划使用场景：寻求最优解。

#初始化 base case
dp[0][0][...] = base
#进行状态转移
for 状态1 in 状态1的所有取值：
	for 状态2 in 状态2的所有取值：
		for ...
			dp[状态1][状态2][...] = 求最值(选择1,选择2...)

当然动态规划的问题也可以通过回溯算法暴力求解。

1.动态规划

动态规划【Dynamic Programming，DP】三要素：通过分析发现题目存在重叠子问题【剪枝优化】以及最优子结构则可以确定为动态规划问题。

• 最优子结构：动态规划将一个复杂的问题分解成若干个子问题，通过综合子问题的最优解来得到原问题的最优解。（“分”与“合”体现在 状态转移方程）。
• 重叠子问题：动态规划会将每个求解过的子问题的解记录【dp数组】下来，这样当下一次碰到同样的子问题时，就可以直接使用之前记录的结果，而不是重复计算。（虽然动态规划使用这种方式来提高计算效率，但不能说这种做法就是动态规划的核心）。

大概包含以下4个概要：重叠子问题（不具有独立性，互相依赖）、最优子结构、状态转移方程、求最值问题。

解析思路：明确「状态」、明确「选择」、明确dp函数/数组的定义、明确base case。?

难点：

1. 首先需要给每个状态赋予实际意义。
2. 根据状态推断出状态转移方程。
3. 确认初始化值，即状态转移方程中dp元素的初始值。不管暴力求解还是动态规划求解，初始值是终止嵌套流程的关键条件。