见微知著：从“爬楼梯”观动态规划初步-创新互联

自主学习了一段时间的算法后，我终于体会到了编程的真正难点。分治、差分、高精度、动态规划……算法实在是太多、太杂、太难了。前不久我参加了力扣的单双周赛和学校举办的新生竞赛，都取得了一定成绩，但也都并不能让我满意。我认识到：编程的学习是没有止境的，比自己强的人太多太多了。

  我想算法的学习总是从最基础最简单的部分开始进行的，所以就动态规划这一我认为相当难的部分而言，从一个简单的小题目进行总结或许是个不错的选择。它就是“爬楼梯”。

第一步：猜想

  这是力扣上面的一个简单题目，我们可以根据题干很容易得出爬楼梯的方法一定是一步和两步的某种顺序组合，例如爬三级楼梯可以是12、21，爬五级楼梯可以是11111、122、121……既然如此，那么枚举这样的方法我们很容易就可以想到，但是事实上却不容易实现。于是我们可以尝试着总结题目的数学规律。通过列举出一些数据，我们可以发现爬某一级楼梯的方法数一定等于前两级楼梯方法数的总和，即 f(N) = f(N-1) + f(N-2) ，这和斐波那契数列相吻合。那么就可以尝试用经典的斐波那契数列的递归方式来解决这道题。

第二步：递归

int Fibonacci(int n)
{
	if (n == 1)return 1;
	if (n == 2)return 2;
	return Fibonacci(n - 1) + Fibonacci(n - 2);
}
int main()
{
	int n;
	cin >>n;
	cout<< Fibonacci(n);
	return 0;
}

  很遗憾的是，用这样的方法在力扣上面作答，结果是超时。原因是因为这样的方式不够便捷，程序在运行得到最终的答案之前往往会多次运算同一组数据，造成了时间上的浪费。怎样才能优化递归程序，在更短的时间内得到答案呢？

第三步：优化递归——记忆化搜索

  对比人类的计算，我们不难发现，对于同一组数据的再次运算，我们只需要在脑海里面提取出相关信息的记忆即可。那么计算机显然也可以通过这样的方式来优化程序的执行。我们只需要一个特定的数组，保存下已经计算过的递归结果，就可以让程序少走弯路，更快得出答案。

int memory[50] = { 0 };
int Fibonacci(int n)
{
	if (n == 1)return 1;
	if (n == 2)return 2;
	if (memory[n] == 0) {
		memory[n]=Fibonacci(n - 1) + Fibonacci(n - 2);
	}
	return memory[n];
}
int main()
{
	int n;
	cin >>n;
	cout<< Fibonacci(n);
	return 0;
}

  用一个或多个数组，抑或是其他形式保存下已经得到的结果，可以省下很大一部分时间，让程序高效运行。不过就像我们人类的记忆一样，程序运行结果的保存也需要额外占据新的空间，所以这是一种空间换时间的方法。

  那有没有不用额外占据空间的方法呢？也是有的，那便是与递归方法方向相反的递推法。

第四步：递推法

  递归法的执行情况可以概括为：输入数据——向深层递归——达到基线条件——逐层返回数据——得到结果。如果我们可以省去深层递归的步骤，直接从基线层层推导得到答案，不仅可以很好的节省时间，更可以节省空间。

int main()
{
	int n;
	cin >>n;
	int dp[50] = { 0 };
	dp[1] = 1;
	dp[2] = 2;
	for (int i = 3; i<= n; i++)
	{
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	cout<< dp[n];
	return 0;
}

  我们可以很直观地感受到程序变得简洁，实际上执行起来也是如此。递推法往往是使用动态规划的最优解，但它通常也是最难直接想到的。一般说来，在解题时我们都会经历以上的一个思维渐进过程，最后得到理想的结果。
总结 
动态规划的难点就在于找出题目中的状态转移条件，它往往是比较抽象的。我们需要在充分熟悉数据特性之后才能总结得出。此外，动态规划还时常会和其他算法相结合，最后把题目组装成为一个“巨无霸”。例如洛谷上面同样出现的爬楼梯题目，就需要综合使用高精度的算法。

虽然说动态规划难，但是它的重要性是所有算法中数一数二的，因此我们都必须尽力掌握。在解决一道动态规划的难题后，心中的成就感会成为你继续学习的动力。学习编程的所有人，我们共勉！

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧