C++DP的学习笔记

一、动态规划基础概念

定义：动态规划（Dynamic Programming，简称 DP）是一种解决多阶段决策问题的数学优化方法。它将原问题分解成若干个子问题，通过解决子问题并将结果保存下来，避免重复计算，提高算法效率。

二、适用问题特点

1.最优子结构：问题的最优解所包含的子问题的解也是最优的，局部最优解能决定全局最优解。

2.子问题重叠：子问题被重复求解，如斐波那契数列中，计算F(n)时，F(n-1)和F(n-2)等子问题会被多次计算。

三、动态规划解题步骤

1.确定 dp 数组及下标的含义：明确dp数组用来存储什么信息，以及数组下标的意义。例如在背包问题中，dp[i][j]可能表示前i个物品放入容量为j的背包中所能获得的最大价值。

2.确定状态转移方程：这是动态规划的关键，找到如何通过已知子问题的解推导出当前问题的解。比如在 01 背包问题中，dp[i][j] = max(dp[i-1][j-w[i]] + c[i], dp[i-1][j])。

3.dp 数组初始化：根据问题的边界条件，给dp数组赋初值。如在 01 背包中，dp[0][j] = 0表示没有物品时，无论背包容量多大，价值都为 0。

4.确定遍历顺序：确定是先遍历物品还是先遍历背包容量等，不同的问题有不同的合适遍历顺序。如 01 背包通常先遍历物品，再遍历背包容量，且背包容量要倒序遍历。

四、动态规划常见类型

1.斐波那契数列类型：包括斐波那契数列、爬楼梯、最小费用爬楼梯、泰波那契数、打家劫舍等。

2.矩阵类型题：最小路径和、不同路径、下降路径最小和、最大正方形等。

3.背包问题：01 背包、01 背包滚动数组、分割等和子集、零钱兑换、一和零等。 4.子序列问题：最长上升子序列、最长增长子序列、最长连续递增子序列、最长公共子序列、最长回文子串、编辑距离、单词拆分等。

5.股票问题：买卖股票最佳时机系列，包括买卖一次、买卖多次、买卖两次、买卖多次有手续费、买卖多次有冻结时间等。

五、动态规划与其他算法思想的区别

与分治思想

相似点：都能将问题分解为子问题求解。 不同点：动态规划解决的问题有重复子问题，且用于求解最优化问题；分治问题不一定有重复子问题，也不一定是最优化问题。

与贪心思想

相似点：都能分解为子问题求解。 不同点：贪心基于最优化策略，由局部最优推全局最优，需证明策略正确性；动态规划求得的一定是最优解，无需证明。