【算法】一文带你快速入门动态规划算法以及动规中的空间优化

君兮_的个人主页

即使走的再远，也勿忘启程时的初心

C/C++ 游戏开发

Hello,米娜桑们，这里是君兮_，如果给算法的难度和复杂度排一个排名，那么动态规划算法一定名列前茅。在最开始没有什么整体的方法的时候，我也曾经被动态规划折磨过很长时间，通过我一段时间的刷题和不断的学习，逐渐有了一套自己有关动态规划算法的心得和经验，今天就通过一些比较简单的题目带大家快速上手动态规划算法

• 好了废话不多说，开始我们今天的学习吧！！

  动态规划算法

  • 一 什么是动态规划算法
  • • 动态规划算法的大致公式
    • 1 求第 N 个泰波那契数
    • • 算法原理解析
      • 编写代码
      • 2 解码方法
      • • 算法原理解析
        • 编写代码
        • 二 空间优化（背包问题）
        • 总结

          一 什么是动态规划算法

          • 动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。
          • 动态规划算法的基本思想是：将原问题分解为若干个子问题，逐个求解子问题，记录每个子问题的解，避免重复计算，最终得到原问题的解。动态规划算法通常用于具有重叠子问题和最优子结构性质的问题，
          • 好了，相信上面这段话没有基础你应该是看不懂的，我们直接说人话
          • 动态规划算法适用于把一个复杂的问题分解成多个子问题，通过解决子问题的方式得到有关原问题的有效信息，最终通过不断的递推得到原问题的解
          • 核心思想就是分治或者说递推，从题目中给的有效信息中最终推出我们想要的结果

            ---

            动态规划算法的大致公式

            不必严格照着这个公式走，前面的步骤是一样，后面的步骤具体问题具体分析即可

            • 1.状态表示

              分析题目，根据题目的要求找出相同的子问题。找出dp表（一般是一维数组或者二维数组）里面的值的含义是什么？（一般都是我们要求的量）

              
              （图片来源网络，侵删）

            • 2.状态转移方程

              分析子问题之间的联系（及dp表里各位置中的值的联系），推出一个类似于递推公式的状态转移方程。

            • [x]3.初始化

              为了保证我们在填dp表时不出现越界访问这种情况，我们需要对边界值进行判断以及通过有效信息来对dp表中的边界值进行初始化

            • 4.填表顺序

              在进行上述的几步操作后，我们需要把我们的dp表填满来解决实际问题了，此时是从大到小填还是从小到大填，我们要根据上述操作得到的有效信息结合题目实际具体判断

              
              （图片来源网络，侵删）

            • 5.返回值

              把dp表填满后，我们要结合题目要求确定返回值来解题了

            • 我知道，在这里干讲方法没人能听的懂，下面就通过上述这个解题方法带大家来解决几个实际问题。

              ---

              1 求第 N 个泰波那契数

              • 原题leetcode链接在这里 第 N 个泰波那契数

                

              • 这个可谓是最经典又最简单的动态规划算法题目了，正合适带大家入门，下面我来带大家分析一下题目

                算法原理解析

                • 1 状态表示

                  给一个整数n 要求我们返回第n个泰波那契数，那么毫无疑问，我们的dp表中的每一个位置表示的就是当n等于这个数时此时的泰波那契数了，也就是 dp[ i ] 表示第i个泰波那契数。

                • 2.状态转移方程

                  找出各个dp[i]的值之间的联系，这个题目已经告诉我们了，第i个泰波那契数就是前三个泰波那契数之和，因此我们可以列出下面这个状态转移方程

                         dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
                  

                  • 3.初始化

                    确定dp表的状态转移方程后，我们为了防止越界需要对边界加以判断

                    数组的下标是从0开始的 因此当我们对i public: int tribonacci(int n) { //对可能出现的越界问题进行判断 if(n==0)return 0; if(n==1||n==2)return 1; //建立dp表 vector //通过状态转移方程，由已知的dp值推出未知的 dp[i]=dp[i-1]+dp[i-2]+dp[i-3]; } //返回第n个泰波那契数 return dp[n]; } }; public: int numDecodings(string s) { //创建dp表 //状态转换方程 //初始化 int n=s.size(); //处理边界条件 if(n==1) { return s[0]!='0'; } vector if(s[i]!='0') dp[i]+=dp[i-1]; t=(s[i-1]-'0')*10+s[i]-'0'; if(t=10&&t // if(s[i-1]!='0') // dp[i]+=dp[i-1]; // int t=(s[i-2]-'0')*10+s[i-1]-'0'; // if(t=10&&t public: int tribonacci(int n) { //含背包机制的空间优化的动态规划算法 int a=0; int b=1,c=1; int d=0; if(n==0)return 0; if(n==1||n==2)return 1; for(int i=3;i d=a+b+c; a=b; b=c; c=d; } return d; } };

本网站所收集的部分公开资料来源于AI生成和互联网，转载的目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。