《算法竞赛入门到进阶》DP学习（1）

动态规划学习（1）

《算法竞赛入门到进阶》学习。

《算法竞赛入门到进阶》

1. 动态规划的概念和思想

DP（Dynamic Programming）是一种算法思想，不是一个特定的算法。

DP 与分治法的区别：

• 分治法是将问题分成独立的子问题，每个子问题能独立解决
• DP 的子问题是相关的，前面子问题的解决结果被后面的子问题使用。

求解 DP 有 3 步：定义状态、状态转移、算法实现。

2. 基础DP

包括硬币问题、0/1 背包、完全背包、最长公共子序列（LCS）、最长递增子序列（LIS）等经典问题。