动态规划 动态规划题目的特点: 计数: 有多少种方式走到右下角 有多少种方法选出 K 个数使得和是 sum 求最大最小值 从左下角到右下角路径的最大数字之和 最长上升子序列长度 求存在性 取石子游戏,先手是否必胜 能不能选出 K 个数使得和是 sum 动态规划组成一:确定状态 状态在动态规划中属于定海神针 简单来说,解动态规划的时候需要开一个数组,确定数组中的每个元素 f[i]或者 f[i][j]需要代表什么,类似于解数学题中的 x,y,z。 确定状态需要 2 个意识:分别是最后一步和子问题