十，算法-动态规划

递归的效率

在 九，算法-递归-CSDN博客中讨论了递归函数的阅读、书写方法，同时也简单阐述了计算机中调用递归函数的方式，无限递归会导致内存溢出的问题。除了无限递归，还有一种情况也会导致递归的执行效率变得很低，示例如下：

int max(const std::vector<int>& array) {
	if (array.size() == 1) {
		return array[0];
	}

	if (array[0] > max(std::vector<int>(array.begin() + 1, array.end() ))) {
		return array[0];
	}
	else {
		return max(std::vector<int>(array.begin() + 1, array.end()));
	}
}

代码中if语句中都调用了一次max(std::vector<int>(array.begin() + 1, array.end()))， 乍看之下没什么问题，但这是一个递归调用，每次对max的调用都会触发一系列的递归调用，以一个数组[1,2,3,4]来对这个递归函数进行分析：

• 基准情形：max({4})，直接返回1；
• 基准情形的上一情形：max({3，4})，该过程中重复调用两次max({4})；
• 继续分析：max({2， 3，4})，则max({3，4})被调用两次，max({4})被调用4次；
• 再往上分析一层：max({1,2,3,4})，max函数将会被调用15次。

如果数据量变为N，则max的时间复杂度近似于。怎么降低其执行的时间复杂度？使用变量存储中间调用过程的数值。将计算结果保存在变量中可以避免多余的递归调用，从而加快递归执行效率。

重复子问题

上述的max函数中重复递归的部分，其调用实参相同，只是重复调用；那么同时存在两次max函数的调用，且实参不同的情况该怎么处理呢？这里以实现斐波那契数为例：

int fib(int n) {
	if (n == 0 || n == 1) {
		return n;
	}

	return fib(n - 2) + fib(n - 1);
}

此处，在递归函数体内调用自身两次，且重复调用较多，时间复杂度近似，这就是重复子问题。解决重复子问题的方法就是动态规划。

动态规划

动态规划是一种优化有重复子问题的递归问题的过程。通过动态规划优化算法有两种基本方法：记忆化和自下而上。

记忆化

记忆化的方法本质上和通过变量存储计算数值的方法相同，即记录过往计算过的函数来减少递归调用。比较适合用来记录计算过的数值的数据结构即哈希表。重复子问题的根源就在于重复进行相同的递归调用，而记忆化机通过哈希表记录每个新计算结果（递归函数调用结果）用来出现重复调用时使用。实现的方法就是在fib函数中增加一个哈希表参数，修改如下：

int fib(int n, std::unordered_map<int, int>& maps) {
	if (n == 0 || n == 1) {
		return n;
	}
	if (maps.find(n) == maps.end()) {
		maps[n] = fib(n - 2, maps) + fib(n - 1, maps);
	}
	return maps[n];
}

通过记忆化的方法，可以将时间复杂度降低到O(N)。

自下而上

自下而上就是放弃递归方法（哭笑不得的表情）。这不是在搞笑，因为动态规划的定义就是优化有重复子问题的递归问题的过程，修改代码如下：

int fib(int n) {
	if (n == 0) {
		return 0;
	}

	int a = 0;
	int b = 1;
	for (int i{ 1 }; i <= n; ++i) {
		int temp{ a };
		a = b;
		b = temp + a;
	}

	return b;
}

选择记忆化还是自下而上，本质上就是在选择是否要使用递归。如果递归的解法更加直观，则可以用记忆化的递归方法来解决问题，否则自下而上的方法通常是更好的选择。