前言 最近和朋友聊天，说起DP问题，想到大学时候学长上来一通“状态转移函数”把我们讲懵了，于是尝试写个入门笔记。 DP思想 通俗来说，动态规划解决问题的方法，就是当系统处于任何一个状态C，你去穷举所有状态A，然后把可能从A到达C的情况全部找出来，并从中获得最优解即可。所以，所谓的“状态转移方程”就是存在一条边从状态A到状态C，这条边的代价。简而言之，动态规划主要思想就是自底向上、局部最优到全局最优，通过计算每个子结构的最优解，求出总体结构的最优解。其目的是解决通过自顶向下的算法（如递归），带来的子结构重复计算，导致时间复杂度指数级上升的问题。 入门示例 桌上有 1kg、8kg、11kg...