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