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

一、动态规划的算法原理

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

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

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

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

class Solution {
public:
    int tribonacci(int n) 
    {
        vector<int> 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 <= n; i++)
        {
            v1[i] = v1[i-1] + v1[i-2] + v1[i-3];
        }
        return v1[n];
    }
};

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

解析： 

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

class Solution {
public:
    int waysToStep(int n) 
    {
        //创建dp表
        vector<int> 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 <= n; i++)
        {
            //确定状态转移方程，这里需要注意，加数的和可能会越界，根据题目要求要对1000000007取模
            v1[i] = ((v1[i-1] + v1[i-2]) % 1000000007 + v1[i-3])%1000000007;
        } 
        return v1[n];
    }
};

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

解析： 

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

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) 
    {
        int length = cost.size();
        //dp表
        vector<int> MinCost(length);
        //初始化
        for(int i = 0; i<cost.size(); i++)
        {
            MinCost[i] = cost[i];
        }
        //状态转移方程
        for(int i = 2; i<length; i++)
        {
            if(MinCost[i-1] < MinCost[i-2])
            {
                MinCost[i] += MinCost[i-1];
            }
            else
            {
                MinCost[i] += MinCost[i-2];
            }
        }
        if(MinCost[cost.size() - 1] < MinCost[cost.size() - 2])
        {
            return MinCost[cost.size() - 1];
        }
        else
        {
            return MinCost[cost.size() - 2];
        }
    }
};

 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; i<len; i++)
        {
            arr[i] = str[i] - 48;
        }
        //处理特殊情况
        if(arr[0] == 0)
        {
            return 0;
        }
        else if(len == 1 && arr[0] != 0)
        {
            return 1;
        }
        for(int i = 1; i<len; i++)
        {
            //例：30
            if(arr[i] == 0 && (arr[i-1] >2))
            {
                return 0;
            }
            //例：1001
            else if(i+1 < len && arr[i] == 0 && arr[i+1] == 0)
            {
                return 0;
            }
        }
        for(int i = 0; i<len; i++)
        {
            cout << arr[i] << " ";
        }
        //dp表
        vector<int> vect(len+1);
        
        
        //初始化
        vect[0] = 1;vect[1] = 1;
        //状态转移方程
        for(int i = 2; i < vect.size(); i++)
        {
            if(arr[i-1] != 0)
            {
                if(arr[i-2] != 0 && ((arr[i-1] + arr[i-2]*10) <= 26))
                {
                    vect[i] = vect[i-1] + vect[i-2];
                }
                else
                {
                    vect[i] = vect[i-1];
                }
            }
            else
            {
                vect[i] = vect[i-2];
            }
        }
        return vect[len];
    }
};