编程总结

在刷题之前需要反复练习的编程技巧，尤其是手写各类数据结构实现，它们好比就是全真教的上乘武功

解决动态规划问题的核心：找出子问题及其子问题与原问题的关系
找到了子问题以及子问题与原问题的关系，就可以递归地求解子问题了。但重叠的子问题使得直接递归会有很多重复计算，于是就想到记忆化递归法：若能事先确定子问题的范围就可以建表存储子问题的答案。
动态规划算法中关于最优子结构和重复子问题的理解的关键点：

1. 证明问题的方案中包含一种选择，选择之后留下一个或多个子问题
2. 设计子问题的递归描述方式
3. 证明对原问题的最优解包括了对所有子问题的最优解
4. 证明子问题是重叠的（这一步不是动态规划正确性必需的，但是如果子问题无重叠，则效率与一般递归是相同的）

A 解决动态规划问题的思考过程

让我们先从一道例题开始

300. 最长上升子序列
     描述：
     给定一个无序的整数数组，找到其中最长上升子序列的长度。
     示例：
     输入: [10,9,2,5,3,7,101,18]
     输出: 4
     解释: 最长的上升子序列是 [2,3,7,101]，它的长度是4

考虑能否将问题规模减小
将问题规模减小的方式有很多种，一些典型的减小方式是动态规划分类的依据，例如线性，区间，树形等。这里考虑数组上常用的两种思路：

**1. 每次减少一半：**如果每次将问题规模减少一半，原问题有[10,9,2,5]，和[3,7,101,18]，两个子问题的最优解分别为 [2,5] 和 [3,7,101]，但是找不到好的组合方式将两个子问题最优解组合为原问题最优解 [2,5,7,101]。

2. 每次减少一个：记 f(n) 为以第 n 个数结尾的最长子序列，每次减少一个，将原问题分为 f(n-1), f(n−2), …, f(1)，共 n - 1 个子问题。n - 1 = 7 个子问题以及答案如下：

[10, 9, 2, 5, 3, 7, 101] -> [2, 5, 7, 101] (f(7) == 4)
[10, 9, 2, 5, 3, 7] -> [2, 5, 7] (f(6) == 3)
[10, 9, 2, 5, 3] -> [2, 3] (f(5) ==2)
[10, 9, 2, 5] -> [2, 5] (f(4) == 2)
[10, 9, 2] -> [2] (f(3) == 1)
[10, 9] -> [9] (f(2) == 1)
[10] -> [10] (f(1) == 1)
规律就是：

1. 初始值都是1；
2. 当开始递增时，dp[i] = dp[j] + 1，同时更新 max 的值;
   

int lengthOfLIS(int *nums, int numsSize) {
	if (numsSize == 0) {
		return 0;
	}
	int max = 1, i, j;
	int dp[numsSize];
	// dp 数组初始值都为1.
	for (i = 0; i < numsSize; i++) {
		dp[i] = 1;
	}
	// 开始动态递归的修改 dp 数组
	for (i = 1; i < numsSize; i++) {
		for (j = 0; j < i; j++) {
			// 出现了递增的下一项
			if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {
				dp[i] = dp[j] + 1;
				if (dp[i] > max) {
					max = dp[i];
				}
			}
		}
	}

	return max;
}

总结： 解决动态规划问题最难的地方有两点：
如何定义 f(n)
如何通过 f(1), f(2), … f(n−1) 推导出 f(n)，即状态转移方程

B 动态规划与其它算法的关系

这一章我们将会介绍分治和贪心算法的核心思想，并与动态规划算法进行比较。

分治
解决分治问题的时候，思路就是想办法把问题的规模减小，有时候减小一个，有时候减小一半，然后将每个小问题的解以及当前的情况组合起来得出最终的结果。例如归并排序和快速排序，归并排序将要排序的数组平均地分成两半，快速排序将数组随机地分成两半。然后不断地对它们递归地进行处理。

这里存在有最优的子结构，即原数组的排序结果是在子数组排序的结果上组合出来的，但是不存在重复子问题，因为不断地对待排序的数组进行对半分的时候，两半边的数据并不重叠，分别解决左半边和右半边的两个子问题的时候，没有子问题重复出现，这是动态规划和分治的区别。

贪心

1. 关于最优子结构
   贪心：每一步的最优解一定包含上一步的最优解，上一步之前的最优解无需记录
   动态规划：全局最优解中一定包含某个局部最优解，但不一定包含上一步的局部最优解，因此需要记录之前的所有的局部最优解

2. 关于子问题最优解组合成原问题最优解的组合方式
   贪心：如果把所有的子问题看成一棵树的话，贪心从根出发，每次向下遍历最优子树即可，这里的最优是贪心意义上的最优。此时不需要知道一个节点的所有子树情况，于是构不成一棵完整的树
   动态规划：动态规划需要对每一个子树求最优解，直至下面的每一个叶子的值，最后得到一棵完整的树，在所有子树都得到最优解后，将他们组合成答案

3. 结果正确性
   贪心不能保证求得的最后解是最佳的，复杂度低
   动态规划本质是穷举法，可以保证结果是最佳的，复杂