C++中的动态规划算法及常见题⽬汇总什么是动态规划在⾯试过程中如果是求⼀个问题的最优解（通常是最⼤值或者最⼩值），并且该问题能够分解成若⼲个⼦问题，并且⼦问题之间好友重叠的更⼩⼦问题，就可以考虑⽤动态规划来解决这个问题。
动态规划的分类 ⼤多数动态规划问题都可以被归类成两种类型：优化问题和组合问题
优化问题 优化问题就是我们常见的求⼀个问题最优解（最⼤值或者最⼩值）
组合问题 组合问题是希望你弄清楚做某事的数量或者某些事件发⽣的概率两种不同动态规划解决⽅案⾃上⽽下：即从顶端不断地分解问题，知道你看到的问题已经分解到最⼩并已得到解决，之后只⽤返回保存的答案即可
⾃下⽽上：你可以直接开始解决较⼩的⼦问题，从⽽获得最⼩的解决⽅案。在此过程中，你需要保证在解决问题之前先解决⼦问题。这种⽅法叫做表格填充法。
常见的动态规划例⼦
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11. 猜数字⼤⼩
1. 裴波那契数列 裴波那契数列就是典型的组合问题，要求出做某事的数量或者概率
问题分析：对于题⽬中的青蛙爬楼梯问题，初试情况下是只有⼀级台阶时，只有⼀种跳法，只有两级台阶时，有两种跳法，当有n级台
阶时，设n级台阶的跳法总数是f(n),如果第⼀步跳⼀级台阶，则和剩下的n-1级台阶的跳法是⼀样的，如果第⼀级跳两级台阶，则和剩下
的n-2级台阶的跳法是⼀样的，因此最终n级台阶的跳法是f(n)=f(n-1)+f(n-2)，即其是可以被分解为更⼩的⼦问题的，下⾯我们以求解f(10)
为例来分析递归的过程
我们从这张图中不难发现，在这棵树中有很多节点都是重复的，⽽且重复节点会随着n的增⼤⽽急剧增⼤，因此我们采⽤⾃顶向下的⽅
式会有很低的效率，因此我们采⽤⾃下⽽上的⽅法，⾸先根据f(1)和f(2)计算出f(3),再根据f(2)和f(3计算出f(4),以此类推求出f(n)
实现的代码如下
1 int jumpFloor(int number) {
一、动态规划的基本思想
在比较基本的算法设计思想里，动态规划是比较难于理解，难于抽象的一种，但是却又十分重要。动态规划的实质是分治思想和解决冗余，因此它与分治法和贪心法类似，它们都
是将问题的实例分解为更小的、相似的子问题，但是动态规划又有自己的特点。
贪心法的当前选择可能要依赖于已经作出的选择，但不依赖于还未做出的选择和子问题，
因此它的特征是由顶向下，一步一步地做出贪心选择，但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解。相比而言，动态规划则
可以处理不具有贪心实质的问题。
在用分治法解决问题时，由于子问题的数目往往是问题规模的指数函数，因此对时间的消
耗太大。动态规划的思想在于，如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的
答案，这样就可以避免大量的重复计算。由此而来的基本思路是，用一个表记录所有已解
决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。
比较感性的说，其实动态规划的思想是对贪心算法和分治法的一种折衷，它所解决的问题往往不具有可爱的贪心实质，但是各个子问题又不是完全零散的，这时候我们用一定的空
间来换取时间，就可以提高解题的效率。
二、动态规划的基本步骤
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行
解。每一个解都对应于一个值，我们希望找到具有最优值（最大值或最小值）的那个解。
设计一个动态规划算法，通常可以按以下几个步骤进行：
（1）找出最优解的性质，并刻画其结构特征。 （2）递归地定义最优值。
DPP完整教程范文
DPP（Dynamic Programming Practice - 动态规划练习）是一种常用的算法设计技巧，被广泛应用于解决许多涉及最优化问题的算法。在这份完整教程中，我们将通过一个具体的例子来了解DPP的基本原理和使用方法。
一、什么是动态规划？
动态规划是一种自底向上的算法设计方法。它的基本思想是将原始问题划分为若干个子问题，并解决每个子问题以获得最优解。通过保存子问题的解，我们可以避免重复计算，提高算法的效率。
二、动态规划的基本步骤
1.确定状态：
首先，我们需要确定问题的状态。状态通常是原始问题中会变化的变量。在一个问题中，状态可能是一个或多个变量的组合。
2.定义状态转移方程：
然后，我们根据问题的性质，定义初始状态和状态转移方程。状态转移方程描述了子问题之间的关系。
3.确定边界条件：
在大多数情况下，我们都需要确定边界条件，以便在计算状态转移方程时，能够终止递归。
4.计算最优解： 最后，我们使用状态转移方程，从初始状态开始，逐步计算出问题的最优解。通常，我们会使用一个数组来保存每个子问题的解，以避免重复计算。
三、举例说明
让我们通过一个例子来详细说明DPP的使用方法。假设有一个数组，我们要找到它的一个子数组，使得该子数组的元素之和最大。我们可以使用动态规划来解决这个问题。
1.确定状态：
在这个问题中，状态是数组中的元素索引。我们可以用dp[i]来表示以第i个元素结尾的子数组的元素之和的最大值。
2.定义状态转移方程：
对于第i个元素，它可以选择加入之前的子数组，或者创建一个新的子数组。因此，我们可以定义状态转移方程为 dp[i] = max(nums[i],
dp[i-1] + nums[i])。
3.确定边界条件：
当i为0时，dp[0]等于nums[0]。
4.计算最优解：
最后，我们可以通过循环遍历数组，根据状态转移方程计算出dp数组的所有元素，然后返回dp数组中的最大值，即为问题的最优解。
动态规划的状态转移方程
动态规划是一种常用的求解最优化问题的方法，广泛应用于计算机科学、数学和经济学等领域。在动态规划中，状态转移方程是关键步骤，它描述了问题的状态如何从一个状态转移到下一个状态。本文将详细介绍动态规划的状态转移方程及其应用。
一、动态规划的基本原理
动态规划是一种将复杂问题分解成更小且重叠的子问题来求解的方法。它的基本思想是利用已经计算过的子问题的解来求解当前问题的解，从而避免重复计算，提高计算效率。
二、状态转移方程的定义
状态转移方程是动态规划中的重要概念，它描述了问题的状态如何从一个阶段转移到下一个阶段。状态转移方程通常使用递推的方式来表示，即通过已知状态推导出未知状态。在解决最优化问题时，我们通常需要定义一个目标函数，通过优化目标函数来求解最优解。状态转移方程可以将目标函数从一个阶段递推到另一个阶段，从而求解出最优解。
三、状态转移方程的形式
状态转移方程的形式可以根据具体问题的特点灵活定义。一般来说，状态转移方程包括以下几个要素： 1. 状态的定义：将问题划分为若干个阶段，并定义每个阶段的状态。状态可以是一个变量、一个数组或其他数据结构。
2. 状态转移的定义：描述问题的状态如何从一个阶段转移到下一个阶段。状态转移可以使用数学表达式、递归方程或其他形式表示。
3. 初始状态和边界条件：确定问题的起始状态和终止状态，并定义边界条件。
四、举例说明
以经典的背包问题为例，我们来看一下如何使用状态转移方程解决问题。
背包问题是一个经典的组合优化问题，给定一个背包的容量和一组物品，每个物品有一个重量和一个价值，需要选择一些物品放入背包中，使得背包的总重量不超过容量，且总价值最大。
在解决背包问题时，我们可以将其划分为若干个阶段，每个阶段表示选择第i个物品放入背包的决策。我们可以定义一个二维数组dp[i][j]来表示在前i个物品中，背包容量为j时的最大价值。状态转移方程可以表示为：
