1. 算法之 动态规划

编程总结

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

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

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

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

让我们先从一道例题开始

  1. 最长上升子序列
    描述:
    给定一个无序的整数数组,找到其中最长上升子序列的长度。
    示例:
    输入: [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 的值;
    1. 算法之 动态规划
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. 结果正确性
    贪心不能保证求得的最后解是最佳的,复杂度低
    动态规划本质是穷举法,可以保证结果是最佳的,复杂
    1. 算法之 动态规划

上一篇:Java基础_101. 对象的使用


下一篇:算法第五章实践报告