21.动态规划算法

人工智能时代，各国都在大力研究机器人技术，也制造出各种各样的机器人，比如：为了解决男女失衡而制造的美女机器人，假如你参与了某美女机器人的研发，你在这个项目中要求实现一个统计算法：如果美女机器人一次可以上1级台阶，也可以一次上2级台阶。求美女机器人走一个n级台阶总共有多少种走法。

乍一看，无从下手，不急，我们不是讲了分治法嘛？这不是可以乘机表演一下？
启发性思考：

分治法核心思想： 从上往下分析问题，大问题可以分解为子问题，子问题中还有更小的子问题
比如总共有5 级台阶,求有多少种走法；由于机器人一次可以走两级台阶，也可以走一级台阶，所以我们可以分
成两个情况
◆机器人最后一次走了两级台阶，问题变成了“走上一个3 级台阶，有多少种走法？”
◆机器人最后一步走了一级台阶，问题变成了“走一个4 级台阶，有多少种走法？”
我们将求n 级台阶的共有多少种走法用f(n) 来表示，则

f(n) = f(n-1) + f(n-2);
由上可得f(5) = f(4) + f(3);
f(4) = f(3) + f(2);
f(3) = f(2) + f(1);

边界情况分析
走一步台阶时，只有一种走法，所以f(1)=1
走两步台阶时，有两种走法，直接走2 个台阶，分两次每次走1 个台阶，所以f(2)=2
走两个台阶以上可以分解成上面的情况
这符合我们讲解的分治法的思想： 分而治之

代码实现

#include <stdio.h>
#include <stdlib.h>

int WalkCount(int n)
{
	if (n < 0) return 0;

	else if (n == 1) return 1;//一级台阶，一种走法
	else if (n == 2) return 2;//两级台阶，两种走法
	else
	{
		return WalkCount(n - 2) + WalkCount(n - 1);
	}
}

int main()
{
	int n = 0;

	printf("请输入台阶的级数：\n");
	scanf_s("%d", &n);

	printf("走%d级台阶共有%d种走法\n", n, WalkCount(n));
	system("pause");
	return 0;
}

但是，上面的代码中存在很多重复的计算。

比如: f(5) = f(4) + f(3) 计算分成两个分支：
f(4) = f(3)+f(2) = f(2) + f(1) + f(2);
f(3) = f(2) + f(1);
上面阴影的部分就是重复计算的一部分！

◆有没有办法避免重复计算的部分？

其实我们可以从下向上分析推断问题。
f(1) = 1
f(2) = 2
f(3) = f(1) + f(2) = 3
f(4) = f(3) + f(2) = 3 + 2 = 5
f(5) = f(4) + f(3) = 5 + 3 = 8
。。。依次类推。。。
实际求解过程

#include <stdio.h>
#include <stdlib.h>

long long WalkCount2(int n)
{
	long long ret = 0;
	if (n <= 0) return 0;
	if (n == 1) return 1;
	if (n == 2) return 2;

	long long* values = new long long[n + 1];

	values[0] = 0;
	values[1] = 1;
	values[2] = 2;

	for (long long i = 3; i <= n; i++)
	{
		values[i] = values[i - 1] + values[i - 2];
	}

	ret = values[n];
	delete []values;

	return ret;
}

int main()
{
	int n = 0;

	printf("请输入台阶的级数：\n");
	scanf_s("%d", &n);

	for (int i = 0; i < n; i++)
	{
		printf("走%d级台阶共有%lld种走法\n", i, WalkCount2(i));
	}

	system("pause");
	return 0;
}

这就是动态规划法!!!
动态规划也是一种分治思想，但与分治算法不同的是，分治算法是把原问题分解为若干子问题，自顶向下，求解各子问题，合并子问题的解从而得到原问题的解。动态规划也是自顶向下把原问题分解为若干子问题，不同的是，然后自底向上，先求解最小的子问题，把结果存储在表格中，在求解大的子问题时，直接从表格中查询小的子问题的解，避免重复计算，从而提高算法效率。

什么时候要用动态规划？
如果要求一个问题的最优解（通常是最大值或者最小值），而且该问题能够分解成若干个子问题，并且小问题之间也存在重叠的子问题，则考虑采用动态规划。

怎么使用动态规划？
五步曲解决：

1. 判题题意是否为找出一个问题的最优解
2. 从上往下分析问题，大问题可以分解为子问题，子问题中还有更小的子问题
3. 从下往上分析问题，找出这些问题之间的关联（状态转移方程）
4. 讨论底层的边界问题
5. 解决问题（通常使用数组进行迭代求出最优解）

课后习题： 给你一根长度为n 的金条，请把金条剪成m 段(m和n都是整数，n>1 并且m>1)每断金条的长度记为k[0],k[1],…,k[m-1]。请问k[0] k[1]…k[m-1]可能的最大乘积是多少？

参考资料来源：

奇牛学院