动态规划——详解斐波那契数列模型（爬楼梯最小花费和解码方法）

         一、快速上手dp表的建立和求得状态转移方程

��      我将此类动态规划问题称为建立dp表问题，方法较为固定，只要走好：

1：建立dp表；

2：初始化（是为了考虑在填表阶段不会出现越界的情况，并且初始化的是dp表的值）；

3：填表；

4：返回值（只要主意好要求返回的是表中最后一个数据还是前一个数据就ok）；

这四步的总结适用于各类斐波那契额数列模型的问题，我将用以下两个问题分别用两种解题思路来进行剖析。

      对于此题，我们来分析他的状态，是让求最后下标为i的位置的总花费。

   第三步，我们来书写状态转移方程：用之前或之后的状态来推导出dp[i]的值，从而得到这个状态转移方程。

    理论上，只要我们能求出这类题型的所有状态转移方程，我们就可以求出关于这类所有的解决方案。

   第四步，其次就是初始化 填表顺序，以及返回值。

    该题通过观察状态转移方程，求出dp[i]就要求出dp[i-1]和dp[i-2]中的最小值,那么就是要从左往右来求出dp[i]的结果。

    最后就是返回值，因为该题说明是求小标为n的最小花费，那么就是这个dp表的最后一个下标，那么就是返回 dp[n];

    接下来就是代码的编写情况：

class Solution {public:    int minCostClimbingStairs(vector& cost) {        //1.建立dp表        //2.初始化        //3.填表        //4.返回值        int n=cost.size();        vector dp(n+1);        for(int i=2;i=0;i--)        {            dp[i]=cost[i]+min(dp[i+1],dp[i+2]);        }        return min(dp[0],dp[1]);    }};

二、（91、）解码方法

我们还是一样，首先观察题意，进行

1、状态表示；2、状态转移表达式的书写；3、初始化；4、确定填表顺序；5、确定返回值

    

class Solution {public:    int numDecodings(string s) {        //1.建立dp表        //2.初始化//就是为了不在填表的时候越界 会用到v[i-1] 和 v[i-2]的值 v[1] 有一种情况就是都能单独解码，但是不能同时解码，算一种情况        //3.填表        //4.返回值        int n=s.size();        vector v(n);        //初始化 一直以来初始化都是初始化v[1]与v[0]这两个值        v[0]=s[0]!='0';        if(n==1)        return v[0];        //如果第一个位置和第二个位置都能单独解码        if(s[0]!='0'&&s[1]!='0')        v[1]+=1;        //如果第一和第二个位置能组合解码        int t=(s[0]-'0')*10+s[1]-'0';        if(t>=10&&t