题目 1. 问题类： 路径问题 路径数量 最小路径 1. 路径数量 m x n 网格的左上角到右下角有多少条路径，要求只能向下或者向右？ 状态定义： 定义fi为到达位置 (i,j) 的不同路径数量。 起始条件： f0=1; 状态转移方程： 当前位置只能 ...

状压 DP 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。 题目： 1125. 最小的必要团队 ` 作为项目经理，你规划了一份需求的技能清单 req_skills，并打算从备选人员名单 people 中选出些人组成一个「必要团队」（ ...

1. 概念 动态规划（Dynamic Programming），是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划是一种方法论，而不是一种具体的算法。 动态规划通过将问题进行拆分成可解决的子问题，从而解决问题。 子问题类型： 子问题之间如果是并行的，则需要采取分治 子问题之间如果有依赖，则需要采取动态规划 动态规划要 ...

定义 区间类动态规划是线性规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系 令状态 f(i,j) 表示将下标位置 i 到 j 的所有元素合并能获得的价值的最大值， 那么 `math f(i,j)= max \{ f(i,k) + f(k+1,j) + cost \} ` cost 为将这两组元素 ...