动态规划-斐波那契数列模子

动态规划（Dynamic Programming, DP）是一种在数学、盘算机科学和经济学中使用的，通过把原标题分解为相对简单的子标题标方式来求解复杂标题标方法。动态规划经常实用于有重叠子标题和最优子布局性子的标题。
1.根本头脑

• 最优子布局：标题标最优解包罗其子标题标最优解。这意味着，假如我们能找到子标题标最优解，我们就可以通过组合这些子标题标解来找到整个标题标最优解。
  
• 重叠子标题：在求解标题标过程中，类似的子标题会被重复求解多次。动态规划通过生存这些子标题标解（通常是在一个数组或哈希表中），从而克制了大量的重复盘算。
  

2.动态规划的范例

• 线性动态规划：子标题标解只依赖于前一个或前几个子标题标解。比方，斐波那契数列、背包标题（0/1背包、完全背包等）、最长上升子序列等。
  
• 区间动态规划：子标题标解依赖于某个区间内的子标题标解。比方，矩阵链乘法、石子归并等。
  
• 树形动态规划：子标题标解依赖于树形布局中的子节点的解。比方，树的直径、树的最大独立集等。
  
• 图论动态规划：子标题标解依赖于图布局中的邻人节点的解。比方，最短路径标题（固然通常使用其他算法如Dijkstra或Bellman-Ford求解，但也可以看作一种特别的动态规划）、状态压缩DP（用于办理某些特别的图论标题）。
  

3.动态规划的根本步调

• 界说状态体现：dp表内里的值体现的寄义。
  怎么来？：
          1.标题要求
          2.履历+标题要求
          3.分析标题标过程中发现重复子标题
  
• 状态转移方程：我们须要找到一种方式，根据子标题标解来构造出整个标题标解。这通常是通过一个或多个状态转移方程来实现的。
  
• 初始化：包管填表的时间不发生越界。
  
• 填表次序：包管填表次序准确，填写当前状态时，须要的状态已经盘算过了。
  
• 返回值：确定准确的返回值。
  

4.动态规划的优缺点

长处：

• 可以大概高效地办理具有重叠子标题和最优子布局的标题。
  
• 相对于暴力搜索，动态规划可以大概显着淘汰盘算量。
  

缺点：

• 须要找到标题标最优子布局和重叠子标题，这偶然并不轻易。
  
• 对于某些标题，动态规划的空间复杂度大概很高（比方，须要生存全部子标题标解）。
  
• 动态规划通常只能找到标题标最优解（或近似最优解），而不能给出全部大概的解。
  

动态规划是一种非常强大的算法操持技能，但它也须要肯定的履历和本领来准确地应用。在实践中，动态规划通常与其他算法和技能团结使用，以办理更复杂的标题。
5.例题

5.1第 N 个泰波那契数

   泰波那契序列 Tn 界说如下： 
  T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
  给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
  示例 1：

1. <strong>输入：</strong>n = 4
2. <strong>输出：</strong>4
3. <strong>解释：</strong>
4. T_3 = 0 + 1 + 1 = 2
5. T_4 = 1 + 1 + 2 = 4

复制代码

示例 2：

1. <strong>输入：</strong>n = 25
2. <strong>输出：</strong>1389537

复制代码

   解法(动态规划)
算法流程（按照根本步调一步步来分析）
1.状态体现:
        这道题可以「根据标题标要求」直接界说出状态体现:
        dp 体现:第 i 个泰波那契数的值。
2.状态转移方程:
        标题已经非常知心的告诉我们了:
        dp = dp[i-1] + dp[i-2] + dp[i - 3]
3.初始化:
        从我们的递推公式可以看出，dp 在 i=0 以及 i=1 的时间是没有办法举行推导的，由于 dp[-2]或 dp[-1] 不是一个有效的数据。因此我们须要在填表之前，将 0，1，2位置的值初始化。标题中已经告诉我们 dp[0]= 0，dp[1] = dp[2] = 1。
4.填表次序:
        毫无疑问是「从左往右」。
5.返回值:
        应该返回 dp[n] 的值。

1. class Solution {
2. public:
3.     int tribonacci(int n) {
4.         if(n==0)
5.             return 0;
6.         if(n==1||n==2)
7.             return 1;
8.         vector<int> dp(n+1);
9.         dp[0]=0;dp[1]=1;dp[2]=1;//初始化
10.         for(int i=3;i<=n;i++)
11.         {
12.             dp[i]=dp[i-1]+dp[i-2]+dp[i-3];//状态转移方程
13.         }
14.         return dp[n];//返回值
15.     }
16. };

复制代码

5.2三步标题

   三步标题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，盘算小孩有多少种上楼梯的方式。效果大概很大，你须要对效果模1000000007。
  示例1:

1. <strong> 输入</strong>：n = 3
2. <strong> 输出</strong>：4
3. <strong> 说明</strong>: 有四种走法

复制代码

示例2:

1. <strong> 输入</strong>：n = 5
2. <strong> 输出</strong>：13

复制代码

   解法(动态规划)
算法思绪
1.状态体现
        这道题可以根据「履历+标题要求」直接界说出状态体现:
        dp 体现:到达 i 位置时，一共有多少种方法。
2.状态转移方程
        以 i 位置状态的迩来的一步，来分情况讨论:
        假如 dp体现小孩上第 ī 阶楼梯的全部方式，那么它应该即是全部上一步的方式之和:
                i.上一步上一级台阶，dp += dp[i - 1];
                ii.上一步上两级台阶，dp += dp[i - 2];
                iii.上一步上三级台阶，dp += dp[i - 3];综上所述，dp= dp[i- 1]+ dp[i - 2]+ dp[i须要留意的是，这道标题说，由于效果大概很大，须要对效果取模。
                在盘算的时间，三个值全部加起来再取模，即(dp[i+dp[i-2]+ dp[i-3])% MOD是不可取的，n取标题范围内最大值时，网站会报错 signedinteger overflow。
                对于这类须要取模的标题，我们每盘算一次(两个数相加/乘等)，都须要取一次模。否则，万一发生了溢出，我们的答案就错了
3.初始化
        从我们的递推公式可以看出，dp 在i=0，i=1以及 i=2 的时间是没有办法举行推导的，由于 dp[-3] dp[-2] 或 dp[-1] 不是一个有效的数据。因此我们须要在填表之前，将1，2，3位置的值初始化。根据题意，dp[1]=1，dp[2]=2，dp[3]=4。
4.填表次序
        毫无疑问是「从左往右」。 
  5.返回值
          返回到 dp[n] 的值。

1. class Solution {
2. public:
3.     const int MOD=1e9+7;
4.     int waysToStep(int n) {
5.         if(n==1 || n==2)
6.             return n;
7.         if(n==3)
8.             return 4;
9.         vector<int> dp(n+1);
10.         dp[1]=1;dp[2]=2;dp[3]=4;//初始化
11.         for(int i=4;i<=n;i++)
12.         {
13.             dp[i]=((dp[i-1]+dp[i-2])%MOD+dp[i-3])%MOD;//状态转移方程
14.         }
15.         return dp[n];
16.     }
17. };

复制代码

5.3使用最小耗费爬楼梯 

   给你一个整数数组 cost ，此中 cost 是从楼梯第 i 个台阶向上爬须要付出的费用。一旦你付出此费用，即可选择向上爬一个大概两个台阶。
  你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
  请你盘算并返回到达楼梯顶部的最低耗费。
  示例 1：

1. <strong>输入：</strong>cost = [10,<em><strong>15</strong></em>,20]
2. <strong>输出：</strong>15
3. <strong>解释：</strong>你将从下标为 1 的台阶开始。
4. - 支付 15 ，向上爬两个台阶，到达楼梯顶部。
5. 总花费为 15 。

复制代码

示例 2：

1. <strong>输入：</strong>cost = [<em><strong>1</strong></em>,100,<em><strong>1</strong></em>,1,<em><strong>1</strong></em>,100,<em><strong>1</strong></em>,<em><strong>1</strong></em>,100,<em><strong>1</strong></em>]
2. <strong>输出：</strong>6
3. <strong>解释：</strong>你将从下标为 0 的台阶开始。
4. - 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
5. - 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
6. - 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
7. - 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
8. - 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
9. - 支付 1 ，向上爬一个台阶，到达楼梯顶部。
10. 总花费为 6 。

复制代码

   留意留意:
在这道题中，数组内的每-下标[0，n-1]体现的都是楼层，而顶楼的位置实在是在n的位置!!!
解法(动态规划)
算法思绪:
解法一:
1.状态体现:
        这道题可以根据「履历+标题要求」直接界说出状态体现:
        第一种:以 i 位置为末端.....
        dp体现:到达 i 位置时的最小耗费。(留意:到达 i 位置的时间，i 位置的钱不须要算上)
2.状态转移方程:
        根据迩来的一步，分情况讨论:
  

• 先到达 i-1 的位置，然后付出 cost[i- 1]，接下来走一步走到 i 位置：dp[i-1] + csot[i-1];
  
• 先到达 i-2 的位置，然后付出 cost[i- 2]，接下来走一步走到 i 位置：dp[i-2] + csot[i-2]。
  

3.初始化:
        从我们的递推公式可以看出，我们须要先初始化 i=0，以及 i=1位置的值。轻易得到 dp[0]= dp[1] = 0，由于不须要任何耗费，就可以直接站在第 0 层和第 1 层上。
4.填表次序:
        根据「状态转移方程」可得，遍历的次序是「从左往右」
5.返回值:
        根据「状态体现以及标题要求」，须要返回 dp[n]位置的值。 

1. class Solution {
2. public:
3.     int minCostClimbingStairs(vector<int>& cost)
4.     {
5.         int n=cost.size();
6.         vector<int> dp(n+1);//dp表
7.         dp[0]=dp[1]=0;//初始化
8.         for(int i=2;i<=n;i++)
9.         {
10.             //根据状态转移方程填表
11.             dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
12.         }
13.         return dp[n];
14.     }
15. };

复制代码

  解法二:
1.状态体现:
        这道题可以根据「履历+标题要求」直接界说出状态体现:
        第二种:以 i 位置为出发点......
        dp体现:从 i 位置出发，到达楼顶，此时的最小耗费。
2.状态转移方程:
        根据迩来的一步，分情况讨论:
  

• 付出cost，以后走一步，接下来从 i+1 的位置出发到止境: dp[i + 1] + cost
  
• 付出cost，以后走两步，接下来从 i+2 的位置出发到止境:dp[i+2] + cost
  

        我们要的是最小耗费，因此 dp = min(dp[i + 1]，dp[i + 2])+ cost。
3.初始化:
        为了包管填表的时间不越界，我们须要初始化末了两个位置的值，团结状态体现易得:dp[n-1]=cost[n-1]，dp[n-2]=cost[n-2]。
4.填表次序:
        根据「状态转移方程」可得，遍历的次序是「从右往左」。
5.返回值:
        根据「状态体现以及标题要求」，须要返回 dp[n]位置的值。

1. class Solution {
2. public:
3.     int minCostClimbingStairs(vector<int>& cost)
4.     {
5.         int n=cost.size();
6.         vector<int> dp(n);
7.         dp[n-1]=cost[n-1];
8.         dp[n-2]=cost[n-2];
9.         for(int i=n-3;i>=0;i--)
10.         {
11.             dp[i]=min(dp[i+1],dp[i+2])+cost[i];
12.         }
13.         return min(dp[0],dp[1]);
14.     }
15. };

复制代码

 5.4解码方法

   一条包罗字母 A-Z 的消息通过以下映射举行了 编码 ：
  "1" -> 'A'
"2" -> 'B'
...
"25" -> 'Y'
"26" -> 'Z'
  然而，在 解码 已编码的消息时，你意识到有许多差别的方式来解码，由于有些编码被包罗在别的编码当中（"2" 和 "5" 与 "25"）。
  比方，"11106" 可以映射为：
  

• "AAJF" ，将消息分组为 (1, 1, 10, 6)
  
• "KJF" ，将消息分组为 (11, 10, 6)
  
• 消息不能分组为  (1, 11, 06) ，由于 "06" 不是一个正当编码（只有 "6" 是正当的）。
  

留意，大概存在无法解码的字符串。
  给你一个只含数字的 非空 字符串 s ，请盘算并返回 解码 方法的 总数 。假如没有正当的方式解码整个字符串，返回 0。
  标题数据包管答案肯定是一个 32 位 的整数。
  
  示例 1：

1. <strong>输入：</strong>s = "12"
2. <strong>输出：</strong>2
3. <strong>解释：</strong>它可以解码为 "AB"（1 2）或者 "L"（12）。

复制代码

示例 2：

1. <strong>输入：</strong>s = "226"
2. <strong>输出：</strong>3
3. <strong>解释：</strong>它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

复制代码

示例 3：

1. <strong>输入：</strong>s = "06"
2. <strong>输出：</strong>0
3. <strong>解释：</strong>"06" 无法映射到 "F" ，因为存在前导零（"6" 和 "06" 并不等价）。

复制代码

   解法(动态规划)
算法思绪:
类似于斐波那契数列~
1.状态体现:
        根据以往的履历，对于大多数线性 dp，我们履历上都是「以某个位置竣事大概开始」做文章，这里我们继续实行「用i位置为末端」团结「标题要求」来界说状态体现。
        dp体现:字符串中 [0，i]区间上，一共有多少种编码方法。
2.状态转移方程:
        界说好状态体现，我们就可以分析 i 位置的 dp 值，怎样由「前面」大概「反面」的信息推导出来。
        关于 i 位置的编码状态，我们可以分为下面两种情况:
        i.让 i 位置上的数单独解码成一个字母;
        ii.让 i 位置上的数与 i-1 位置上的数团结，解码成一个字母。
下面我们就上面的两种解码情况，继续分析:
让i位置上的数单独解码成一个字母，就存在「解码乐成」和「解码失败」两种情况:
        i.解码乐成:当 i 位置上的数在[1，9]之间的时间，分析 i 位置上的数是可以单独解码的，那么此时[0，i]区间上的解码方法应该即是[0，i- 1]区间上的解码方法。由于[0，i- 1]区间上的全部解码效果，反面填上一个 i 位置解码后的字母就可以了。此时 dp=dp[i-1];
        ii.解码失败:当 i 位置上的数是 0 的时间，分析 i 位置上的数是不能单独解码的，那么此时 [0，i]区间上不存在解码方法。由于 i 位置假如单独到场解码，但是解码失败了，那么前面做的积极就全部白费了。此时 dp=0。 
  让 i 位置上的数与 i- 1 位置上的数团结在一起，解码成一个字母，也存在「解码乐成」和「解码失败」两种情况:
        i.解码乐成:当团结的数在[10，26]之间的时间，分析[i-1，i]两个位置是可以解码乐成的，那么此时[0，i]区间上的解码方法应该即是[0，i- 2]区间上的解码方法，缘故起因同上。此时 dp= dp[i- 2];
        ii.解码失败:当团结的数在[0，9]和[27 ，99]之间的时间，分析两个位置团结后解码失败(这里肯定要留意 00 01 02 03 04这几种情况)，那么此时[0，i]区间上的解码方法就不存在了，缘故起因仍然同上。此时dp=0。
综上所述: dp终极的效果应该是上面四种情况下，解码乐成的两种的累加和(由于我们关心的是解码方法，既然解码失败，就不消到场到终极效果中去)，因此可以得到状态转移方程(dp默认初始化为 0):
        i.当 s上的数在[1，9]区间上时: dp += dp[i-1];
        ii.当 s[i-1]与 s上的数团结后，在[10，26] 之间的时间: dp += dp[i-2];
假如上述两个判定都不建立，分析没有解码方法，dp就是默认值 0。
3.初始化:
方法一(直接初始化):
        由于大概要用到 i-1 以及 i-2 位置上的 dp 值，因此要先初始化「前两个位置」。
初始化 dp[0]：
          i.当s[0] == '0'时，没有编码方法，效果dp[0] = 0。
          ii.当s[0] != '0'时，能编码乐成，效果dp[0] = 1。
  初始化 dp[1]:
          i.当s[1] 在[1 , 9]之间时，能单独编码，此时 dp[1] += dp[0]（缘故起因同上，dp[1]默以为0）
          ii.当s[0] 与s[1] 团结的数在 [10 , 26]之间时，分析在前两个字符中，又有一种编码方式，此时dp[1] += 1
  方法二（添加辅助位置初始化）
          可以在最前面加上一个辅助节点，资助我们初始化。使用这种本领要留意两个点：
          i.辅助节点里的值要包管后续填表是准确的。
          ii.下标的映射关系。
  4.填表次序
          从左往右
  5.返回值
          返回 dp[n-1] 的值，体现在[0 , n-1]区间上的编码方法。
        

1. class Solution {
2. public:
3.     int numDecodings(string s)
4.     {
5.         if(s[0]=='0')
6.             return 0;
7.         int n=s.size();
8.         vector<int> dp(n);
9.         if(s[0]>'0'&&s[0]<='9')
10.             dp[0]=1;
11.         if(n==1)
12.             return dp[0];
13.         if(s[1]>'0'&&s[1]<='9')
14.             dp[1]=1;
15.         int m=(s[0]-'0')*10+s[1]-'0';
16.         if(m>=10&&m<=26)
17.             dp[1]+=1;
18.         for(int i=2;i<n;i++)
19.         {
20.             //单独编码
21.             if(s[i]!='0')
22.             {
23.                 dp[i]+=dp[i-1];
24.             }
25.             //和前面一个数联合起来编码
26.             int m=(s[i-1]-'0')*10+s[i]-'0';
27.             if(m>=10&&m<=26)
28.                 dp[i]+=dp[i-2];
29.         }
30.         return dp[n-1];
31.     }
32. };

复制代码