算法修炼-动态规划之斐波那契数列模型

一、动态规划的算法原理

这是本人动态规划的第一篇文章，所以先阐述一下动态规划的算法原理以及做题步骤。动态规划本人的理解就是通过题目所给的条件正确地填满dp表（一段数组）。首先要先确定好dp表每个位置的值所代表的含义是什么，然后通过题目条件以及经验推出状态转移方程，第三个就是初始化，确定填表顺序以及保证填表不越界，最后输出题目所需的结果，大致就是这个思路。

二、斐波那契数列模型例题分析

1137. 第 N 个泰波那契数 – 力扣（LeetCode）

本题的思路较为简单，状态转移方程已经给出，直接上代码：

class Solution {
public:
    int tribonacci(int n) 
    {
        vector v1(n+1);
        //初始化
        if(n == 1)
        return 1;
        else if(n == 2)
        return 1;
        else if(n == 0)
        return 0;
        v1[0] = 0;
        v1[1] = 1;
        v1[2] = 1;
        
  服务器托管网      for(int i = 3; i 

面试题 08.01. 三步问题 – 力扣（LeetCode）

解析：

假设小孩此时正处于某一台阶上，那他是如何到达这一台阶的呢？是不是他有可能是从该台阶的前一个台阶跳上来的，也可能是从该台阶的前两个台阶跳上来的，也可能是从该台阶的前三个台阶跳上来的，所以小孩到某一台阶就有三种可能情况，也即dp表中某个位置的值就是这个位置前三个位置的值相加，从而确定出了状态转移方程。

class Solution {
public:
    int waysToStep(int n) 
    {
        //创建dp表
        vector v1(n+1);
        if(n ==1)
        return 1;
        if(n == 2)
        return 2;
        if(n == 3)
        return 4;
        //初始化
        v1[1] = 1;v1[2] = 2; v1[3] = 4;
        for(int i = 4; i 

746. 使用最小花费爬楼梯 – 力扣（LeetCode）

解析：

要确定每一级楼梯最低花费，通过比较前两级楼梯，确定应该加的值，从而确定状态转移方程。

class Solution {
public:
    int minCostClimbingStairs(vector& cost) 
    {
        int length = cost.size();
        //dp表
        vector MinCost(length);
        //初始化
        for(int i = 0; i

91. 解码方法 – 力扣（LeetCode）

解析：

选定一个位置作为结尾，如果这个位置的值不为零，就看其能否与前一个位置的值组成合法编码，如果能，这个位置的值就是它的前一个位置加上它的前前一个位置的值，如果不能，这个位置的值就是它的前一个位置的值；如果这个位置的值为零，就看其能否与前一个服务器托管网位置的值组成合法编码，如果能，这个位置的值就是它的前前一个位置的值。

class Solution {
public:
    int numDecodings(string s) 
    {
        int len = s.length();
        int arr[len];
        const char* str;
        str = s.c_str();
        for(int i = 0; i2))
            {
                return 0;
            }
            //例：1001
            else if(i+1  vect(len+1);
        
        
        //初始化
        vect[0] = 1;vect[1] = 1;
        //状态转移方程
        for(int i = 2; i 

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: unittest测试框架详解

交流讨论：欢迎加入我们一起学习！ 资源分享：耗时200+小时精选的「软件测试」资料包 教程推荐：火遍全网的《软件测试》教程 欢迎点赞 收藏 ⭐留言 如有错误敬请指正！ 单元测试的定义 1. 什么是单元测试？ ​ 单元测试是指，对软件中的最小可测试单元在与程序其…