摘要本系列从6道经典的动态规划题入手，去理解动态规划的基本思路和想法，以及动态规划和递归记忆搜索法存在的某些联系，对于每道题目，我们将用两种方法去实现，这里讲解第一道题目，作个开头。前言我们知道，大部分的动态规划题目可以利用递归加记忆搜索法去完成，这两者的程序速度方面并没有较大的区别。动态规划（DP）和记忆化搜索（也称为递归记忆）是两种解决复杂问题的常用技术，它们都利用了子问题的解来构建原问题的解。动态规划是一种自底向上的方法，它首先解决子问题，然后基于子问题的解来解决更大的问题。动态规划通常使用一个表格来存储子问题的解，这样在需要时就可以直接查找，而不需要重新计算。因此，动态规划通常用于最优

💝💝💝欢迎来到我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。推荐:kuan的首页,持续学习,不断总结,共同进步,活到老学到老导航檀越剑指大厂系列:全面总结java核心技术点,如集合,jvm,并发编程redis,kafka,Spring,微服务,Netty等常用开发工具系列:罗列常用的开发工具,如IDEA,Mac,Alfred,electerm,Git,typora,apifox等数据库系列:详细总结了常用数据库mysql技术点,以及工作中遇到的mysql问题等懒人运维系列:总结好用的命令,解放双手

文章目录前言一、钢条切割问题1.问题背景2.问题描述3.问题的难点（1）情况较多（2）消除重复子问题二、问题解决方案1.问题的特点（1）最优化子结构（2）重复子问题2.最优化解决方案（1）自顶向下的普通递归（2）带备忘的自顶向下（3）自底向上3.构建最优解的结构三、C语言代码1.三种方案的函数代码（1）自顶向下的普通递归（2）带备忘的自顶向下（3）自底向上2.整体测试代码总结前言本文主要讲解了钢条切割问题的解决方案，并且给出了C语言代码。其中涉及到了动态规划的思想，会在之后的文章中详细讲解一、钢条切割问题1.问题背景Serling公司购买长钢条，将其切割成短钢条进行出售。切割工序本身没有成本支

文章目录一、钢条切割定义二、具体步骤1.思考2.代码思考3.动态规划求解4.伪代码三：总结：一、钢条切割定义图为价格表给定一段长度是n的钢条和一个价格表，求切割方案使得收益达到最大（允许全不切割的情况存在）二、具体步骤1.思考易知长度为n的钢条有2的n-1次方种选择方式，故不可穷举。我们可以考虑一段长度为n的钢条切段，在第k处时切开，如图：这样的话，在n1段的前k-1上寻找最佳解，同理，在n2段的后m-k上寻找最佳解。这样的话问题就成为了：将两段钢条看成两个独立的钢条问题，我们称钢条切割问题满足最优子结构。还有另一种思路，采用更为简单的递归求解思想：一段长度为i的不可分割的钢条一段长度为n-i

文章目录一、钢条切割定义二、具体步骤1.思考2.代码思考3.动态规划求解4.伪代码三：总结：一、钢条切割定义图为价格表给定一段长度是n的钢条和一个价格表，求切割方案使得收益达到最大（允许全不切割的情况存在）二、具体步骤1.思考易知长度为n的钢条有2的n-1次方种选择方式，故不可穷举。我们可以考虑一段长度为n的钢条切段，在第k处时切开，如图：这样的话，在n1段的前k-1上寻找最佳解，同理，在n2段的后m-k上寻找最佳解。这样的话问题就成为了：将两段钢条看成两个独立的钢条问题，我们称钢条切割问题满足最优子结构。还有另一种思路，采用更为简单的递归求解思想：一段长度为i的不可分割的钢条一段长度为n-i