猫史档案馆

首先,学习动态规划，我们得先知道什么是动态规划？
动态规划与分治方法类似，都是通过组合子问题的解来来求解原问题的。分治方法将问题划分为互不相交的子问题，递归的求解子问题，再将它们的解组合起来，求出原问题的解。

而动态规划与之相反，动态规划应用与子问题重叠的情况，即不同的子问题具有公共的子子问题 (子问题的求解是递归进行的，将其划分为更小的子子问题）。在这种情况下，分治方喵做许多不必要的工作，他会反复求解那些公共子子问题。而动态规划对于每一个子子问题只求解一次，将其解保存在一个表格里面，从而无需每次求解一个子子问题时都重新计算，避免了不必要的计算工作。

下面我们通过几个例子来演示一下这个过程：

[编程题]斐波那契数列
热度指数：374145 时间限制：1秒 空间限制：32768K
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为1）。
n<=39
这个题目相信大家都很熟悉：
在我们学习递归的时候应该都见过：我们先写一个递归版本的。

#include <iostream>
#include <math.h>
using namespace std;
int main()
{
    int k,lo[46];
    lo[0]=1;
    lo[1]=2;
    cin>>k;
    for(int i=2;i<k;i++)
    {
    	lo[i]=lo[i-1]+lo[i-2];
	}
    cout<<lo[k-2];
}

这个代码的时间复杂度是2^n，也就是指数递增，我们经过测试当求一个很大数字的时候，运行就会出错，我们来看一下：
这里写图片描述
没错就是栈溢出：
下来我们用动态规划来求解一下这个问题：
先看按照动态规划步骤的简单分析：

[编程题]喵跳台阶(在上届noc初赛考了图形化版本的)
热度指数：221924时间限制：1秒空间限制：32768K
算法知识视频讲解
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
先来看简单分析：
这里写图片描述

 

本期分享就到这里

关注停更作品的老流,不迷路