动态规划算法的要素

① 算法设计的5种基本方法

步骤/方式1
一、【分治法】
分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
步骤/方式2
二、【动态规划法】
最优化原理是动态规划的基础，任何一个问题，如果失去了这个最优化原理的支持，就不可能用动态规划方法计算。
使用动态规划求解问题，最重要的就是确定动态规划三要素：问题的阶段，每个阶段的状态以及从前一个阶段转化到后一个阶段之间的递推关系。
步骤/方式3
三、【贪心算法】所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。贪心算法的基本思路如下：
1. 建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。
步骤/方式4
四、【回溯法】
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
用回溯法解题的一般步骤：
（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
步骤/方式5
五、【分支限界法】
基本思想 ：分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
常见的两种分支限界法：
（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。
（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

② 算法基础之动态规划法

动态规划法是一种优化方法，用于解决多阶段决策问题，通过分解成单阶段子问题并利用它们之间的关系求解。它与分治法和贪心法类似，但处理的是子问题重叠和共享子子问题的情况。动态规划适用于那些满足特定性质的问题，如子问题之间存在重叠、求解过程可以以先前结果为基础等。

动态规划法解决问题的一般步骤包括：定义状态、确定状态转移方程和计算过程。以多段图问题为例，通过先向后处理求得源点到各个顶点的最短路径，再通过优化处理存储多条最短路径信息。矩阵连乘问题则需找到最小的乘法次数，通过二维数组记录每个阶段的最小乘积次数。最长公共子序列问题则通过二维数组记录子序列长度，对所有可能的组合进行比较。

动态规划问题的时间复杂度通常为多项式级别，如多段图问题为O(E+K)，矩阵连乘问题为O(n^3)，最长公共子序列问题为O(mn)。空间复杂度较高，如多段图问题和矩阵连乘问题为O(V+E)，最长公共子序列问题和优化处理后为O(n)或O(mn)。动态规划实质上是一种以空间换取时间的策略，问题模型需根据问题特性定制。

总结来说，动态规划需要对问题进行深入分析，定义合适的状态和状态转移方程，并注意空间效率的优化。通过理解这些问题的处理方法，可以提高解决复杂问题的能力。感兴趣的朋友可以关注公众号字节幺零二四，获取本文的详细文档和更多实例。

③ dp算法是什么呢

dp算法就是动态规划，是运筹学的一个分支，是求解决策过程最优化的过程。

动态规划方法一般用来求解最优化问题。这类问题可以有很多可行解，每个解都有一个值，我们希望找到具有最优值的解，我们称这样的解为问题的一个最优解，而不是最优解，因为可能有多个解都达到最优值。

动态规划过程介绍：

确定动态规划三要素，整个求解过程就可以用一个最优决策表来描述，最优决策表是一个二维表，其中行表示决策的阶段，列表示问题状态。

表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系，从1行1列开始，以行或者列优先的顺序，依次填写表格，最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。