C++动态规划
动态规划
- 动态规划基础知识
-
- 动态规划问题的特点
- 动态规划的基本思路
- 例题——最长递增子序列问题
-
- 解题思路
- 例题——最长递增子序列问题2
-
- 解题思路
- 例题——01背包问题
-
- 解题思路
动态规划基础知识
动态规划（Dynamic Programming, DP）是C++以及其他编程语言中常用的算法思想，适用于解决具有最优子结构和重叠子问题性质的问题。通过将复杂问题分解为较小的子问题，并保存这些子问题的解来避免重复计算，动态规划可以显著提高效率。
动态规划问题的特点
-
最优子结构：问题的最优解可以由其子问题的最优解推导出来。也就是说，大问题的解可以依赖于小问题的解。
-
重叠子问题：同一个子问题会被多次计算。动态规划通过将子问题的结果保存下来（通常使用数组或哈希表），以避免重复计算。
动态规划的基本思路
动态规划通常采用自底向上的方式，通过求解所有子问题，逐步构建最终问题的解。大多数动态规划问题分为以下几步：
-定义状态：设立数组或其他数据结构来表示子问题的解。
通常通过 dp[i] 来表示问题的某个状态。
-
状态转移方程：根据问题的描述，找到子问题之间的递推关系。
一般形如 dp[i] = f(dp[i-1], dp[i-2], …)。 -
初始条件和边界：确定初始状态的值，即递推