【基础算法】动态规划

递归算法的核心思想是将求解的问题分解成若干具有相同属性的子问题，通过这些子问题的解得到原问题的解。 递归算法的主要缺陷是在递归调用过程中存在冗余的运算，这将增加算法的时间复杂度和空间复杂度。 动态规划算法可以消除这些冗余的计算。 同贪心算法，动态规划也有递归的影子。

走楼梯问题

一个楼梯共有10个台阶，一个人从下往上走，可以一次走1级台阶，也可以一次都2级台阶。请问有多少种方法走完这10级台阶？

如果要走到第10级台阶，则必然会存在且仅存在以下两种情况：

1. 先到第8级台阶，然后向上登上2级台阶。
2. 先到第9级台阶，然后向上登上1级台阶。

有人可能会问，到第8级台阶的时候先登上第9级台阶，再登上第10级台阶，这难道不也是一种情况吗？其实这种情形已经包含在第2种情形中了。这两种情况是根据是否登上第9级台阶划分的，只要登上第9级台阶就属于第2种情况。

递归解决

假设登上第8级台阶的走法有x种，登上第9级的走法有y种，那么很显然，登上第10级的走法有x+y种。 我们可以总结出以下的计算公式：

写出代码，这与斐波那契数列非常像：

int getClimbWays(int n) {
    if (n == 1) {
        return 1;
    }
    else if (n == 2) {
        return 2;
    }
    else {
        return getClimbWays(n - 1) + getClimbWays(n - 2);
    }
}

深入思考不难发现，该算法存在很多冗余计算。 在计算F(n)时要先计算F(n-1)和F(n-2)，而计算F(n-1)时要先计算F(n-2)和F(n-3)，这样就计算了两遍F(n-2)。因此函数getClimbWays()会执行很多次重复冗余的调用。

动态规划

上述递归算法时自顶向下的，从F(10)开始逐级分解该问题，在重复调用自身的同时，问题的规模不断缩小。 其实我们还可以自底向上计算，也就是通过F(1)=1和F(2)=2计算出F(3)=3，再通过F(2)=2和F(3)=3计算出F(4)=5，以此类推，一直计算出F(n)。采用这种方法可以将每一步的计算结果都记录下来，没有冗余计算，效率会高很多。 通常称这种利用问题本身的递归特性，自底向上计算出最优解的方法为动态规划算法。

#include<iostream>
#include<algorithm>
using namespace std;
int getClimbWays(int n) {
	int a = 1;
	int b = 2;
	int tmp = 0;
	int i = 0;
	if (n == 1)return 1;
	else if (n == 2)return 2;
	else {
		for (i = 3; i <= n; i++) {
			tmp = a + b;
			a = b;
			b = tmp;
		}
		return tmp;
	}
}

int main() {
	std::cout << getClimbWays(10);
}

当n>2时，需要通过循环来计算共有多少种走法，该循环就是上面所讲的自底向上的求解过程。

机器人的不同路径

一个机器人位于一个m x n网格的左上角，已知机器人每次只能向下或者向右移动一步，机器人试图达到网格的右下角，请问一共有多少条不同的路径？

设起点为(starti,startj)，终点为(endi,endj)。

递归实现

我们可以从宏观角度自顶向下地考虑这个问题。因为机器人每次只能向下或者向右移动一步，所以从点(starti,startj)出发，下一步可能是(starti+1,startj)向下移动一步，也可能是(starti,startj+1)向右移动一步。可以将起点到终点的路径数表示为这两部分之和。

这样就将一个规模较大的问题划分为两个规模较小的问题，解决这两个规模较小的问题的方式与解决规模较大问题的方法是完全一样的，可以继续向下拆分。这样就构成了解决网格不同路径的递归结构，所以本题最简单直观的解法就是使用递归算法。

int getPathsNumber(int starti, int startj, int endi, int endj) {
	//需要移动的方向只有一个
	if (starti == endi && startj == endj)return 1;
	//超过网格边界，是一种错误情形，返回0
	if (starti > endi || startj > endj)return 0;
	return getPathsNumber(starti + 1, startj, endi, endj) + getPathsNumber(starti, startj + 1, endi, endj);
}

这个问题不难理解，与之前的斐波那契数列非常类似。 在计算过程中存在大量重复和冗余，算法性能不高 ，可以采用动态规划的方法自底向上解决这个问题。

动态规划

要计算从点(starti,startj)到点(endi,endj)的路径数，需要先得到(starti+1,startj)到(endi,endj)的路径数和(starti,startj+1)到(endi,endj)的路径数。 我们可以利用一个与原网格同样大小的矩阵来存储对应网格种每个点到达终点(endi,endj)的路径数。 该矩阵的最后一行和最后一列上的值都是1，因为从对应网格中最后一行或最后一列上的任意点到达终点的路径都只有一条（因为只能向下或向右移动）。所以将矩阵的最后一行和最后一列置为1可作为填写这个矩阵的初始操作。

接下来以矩阵最后一行和最后一列的初始值为基础填写整个矩阵，可以逐行填写或逐列填写，遵循matrix[i,j]=matrix[i+1,j]+matrix[i,j+1]的原则即可，最终得到的(0,0)位置上的值即为本题的答案。

int getPathsNumber(int endi, int endj) {
	int* matrix = (int*)calloc(sizeof(int), endi * endj);
	int i(0), j(0);
	//初始化matrix，遍历的是索引
	for (i = endi, j = 1; j <= endj; j++) {
		matrix[(i - 1) * endj + j - 1] = 1;
	}
	for (i = 1, j = endj; i <= endj; i++) {
		matrix[(i - 1) * endj + j - 1] = 1;
	}
	//逐项填写矩阵
	for (i = endi - 1; i >= 1; i--) {
		for (j = endj - 1; j >= 1; j--) {
			matrix[(i - 1) * endj + j - 1] = matrix[i * endj + j - 1] + matrix[(i - 1) * endj + j];
		}
	}
	//检查数组状态
	for (int i = 1; i <= endi; i++) {
		for (int j = 1; j <= endj; j++) {
			std::cout << matrix[(i - 1) * endj + j - 1] << "\t";
		}
		std::cout << std::endl;
	}
	return matrix[0];
}

上面的C++实现中使用了calloc()方法。 由于C/C++没有对二维数组的封装，所以实现二维数组需要计算下标。 为了方便计算下标，在循环中我遍历的索引，下标就是索引对应元素个数-1。由于涉及二维数组的操作，所以对循环遍历的对象要格外注意：遍历的是索引还是下标，尽量避免混淆。

国王的金矿

有一个国家发现了5个金矿，每座金矿的储量和所需工人数量如下：

现在招募了10名工人参与挖矿，为了便于管理，要求没做金矿要么全挖，要么不挖，不难能只挖一半就停工，也不能排除不符合要求的人数去挖矿。同时为了保密，每名工人只能在一座金矿上挖矿，不能在一座金矿上挖完之后去另一座。 国王希望挖出尽可能多的黄金，但人力有限，又有上述规则的限制，所以不可能每个金矿都被挖掘。最多可以挖到多少黄金？

国王可以把这两个问题拆分成两个子问题，交由两个副手完成，再由自己统一决策：

• 不开采5号金矿，并合理分配10名工人对1~4号金矿进行开采，计算出最多可以开采多少黄金。
• 开采5号金矿，并合理安排剩余的7名工人对1~4号金矿进行开采，计算出1~4号最多可以开采多少黄金。

递归实现

这个公式如果结合上面的分析的话，并不难理解。

• n表示1~n号金矿。
• w表示剩余工人的数量。
• G(n)表示n号金矿生产的数量。
• F(n,w)表示w人挖1~n号金矿的最高产量。

前两个式子是递归的结束条件，此时已经迭代到P[0]，根据剩余的人数确定F(n,w)的值。 第三个式子发现剩余人数无法挖n号金矿，那么则只能继续向前分配。 最后个式子根据剩余人数能不能挖n号金矿，比较挖n号矿和不挖n号矿的产量，取最大值。

int getMostGold(int workers, int* needs, int* yields, int c) {
	//就剩一座金矿，而且人数不够
	if (c == 1 && workers < needs[0]) {
		return 0;
	}
	//就剩一座金矿，人数够了
	if (c == 1 && workers >= needs[0]) {
		return yields[0];
	}
	//这座矿人数不够挖不了，尝试挖前面的金矿
	if (workers < needs[c - 1]) {
		return getMostGold(workers, needs, yields, c - 1);
	}
	//人数够了，判断这座矿挖不挖，那种情况产量更高
	return max(getMostGold(workers, needs, yields, c - 1), getMostGold(workers - needs[c - 1], needs, yields, c - 1) + yields[c - 1]);
}

上述递归算法中，每一步都有两个子进程，也就是需要递归调用两次getMostGold()，对于一个规模为n的问题，该算法的时间复杂度为

。

动态规划

本题满足动态规划的两个基本要素：最优子结构和子问题重叠。 我们可以自底向上逐步递推出每一步的最优解，在使用一些临时变量或表格记录这些子问题的解，这样一步一步向上迭代求出问题的最终解。

首先填写表格的第一行，因为1号金矿需要的人数为5，所以前四个格子填0，后6个格子填产量400。 第2行对应n=2，表示要开采1~2号金矿，需要的人数也为5，当工人数量workers小于人数需求needs[n-1]时，F(n,w)=F(n-1,w)。所以第2行第1~4列都填0。当workers>=needs[n-1]时，需要根据第四个公式计算。 在计算第2行时并不是每一步都调用递归函数，而是通过第1行中的值推算。例如在计算F(2,5)时，我们要求出F(1,5)和F(1,0)+500，这两个值都可以直接在第1行中查出，不需要递归运算，这就是动态规划的精髓所在：不需要重复调用递归函数，只需要在已有的计算结果哦中查找需要的值，可以避免很多冗余的计算。 最后一行最后一列的值即为我们要求的最终结果。

class KingAndGold {
	int P[5] = { 5,5,3,4,3 };
	int G[5] = { 400,500,200,300,350 };
public:
	int getMostGold(int n, int w) {
		int* preResult = (int*)calloc(sizeof(int), w + 1);
		int* result = (int*)calloc(sizeof(int), w + 1);
		//给表格的第一行赋初始值
		for (int i = 0; i < w; i++) {
			if (i < P[0])preResult[i] = 0;
			else preResult[i] = G[0];
		}
		//循环生成其他表格的内容
		for (int i = 1; i < n; i++) {
			for (int j = 1; j <= w; j++) {
				//如果人数不够，把F(n-1,w)落下来
				if (j < P[i])result[j] = preResult[j];
				//如果人数够了，取较大值
				else result[j] = max(preResult[j], preResult[j - P[i]] + G[i]);
			}
			for (int k = 0; k <= w; k++) {
				preResult[k] = result[k];
			}
		}
		return result[w];
	}
};

观察上面的表格会发现，要求第n行，只需要求出第n-1行的内容即可。 所以上面的代码中只是定义了两个数组用于存储两行数据，并没有定义mxn大小的完整矩阵。减少算法的空间复杂度。

总结

动态规划与递归算法的相似之处在于他们都会将一个较大的问题分解为若干较小的问题，逐一求解后再汇聚成一个大的问题。不同之处在是永泰规划算法以自底向上的方式计算最优解，在计算过程中保存已解决的子问题答案，减少冗余的计算，从而提高算法效率。 使用动态规划要把握如下两个基本要素：

• 具备最优子结构
• 具备子问题重叠性质

当一个问题的最优解包含其子问题的最优解时，就称该问题具备最优子结构。在走楼梯问题中，F(n-1)和F(n-2)就是F(n)的最优子结构，因为F(n-1)和F(n-2)就是F(n)的最优解。 在走楼梯中，我们将重叠的F(n-1)和F(n-2)分别用临时变量ab存储，自下而上用循环求解。 在机器人中，求出一个方格的路径需要先得到相邻两个方格的路径，每个方格都会被利用的到，我们使用一个矩阵matrix来存储数据。 在国王的金矿中，我们逐行求解，要求第n行，只需要求出第n-1行的即可，我们使用连个数组分别存储这两行。需要注意的是，这两个数组在交换数据时，并没有使用改变指针方向的方式，是因为这样会导致两个指针指向同一段内存空间，实际是操作同一行的数据而不是两行。