一. 从单纯的递推算法推开状态的一扇门
递推类的题目处理过程:
递推状态定义 （核心, 决定递推公式） f[x] : 符号表达式, 加上这个表达式子的定义
确定递推公式 （k i-----> k i+1） 确定f[x] 究竟依赖哪些 f[y]
初始化init (递推初始状态)
循环或者递归程序实现
按照上述方式对于题目进行刨析:
70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
- 状态定义: dp[i] : 爬上 i 阶楼梯的方法数目
- 状态转移方程: 分析依赖关系 ?? 每一次可以爬上1 或者 2 个台阶, 所以 当你站上 i 阶级台阶的时候, 你的上一个状态 可以是站在 i - 1 阶台阶上, 或者是 i - 2 阶级台阶上的. 图解转移:
- init : f0] = 1; //只有一个方法, 最开始没爬, f[1] = 1 从0层向上爬一层
class Solution { public: int climbStairs(int n) { int f[n + 1]; //init: f[0] = 1; f[1] = 1; for (int i = 2; i <= n; ++i) { f[i] = f[i - 1] + f[i - 2]; } return f[n]; } };
二. 动态规划 和 递推算法 究竟是何关系, 动态规划为何是一种特殊的递推算法?
正如上图所示那样 ： 动态规化一定是递推问题, 但是递推问题不一定是动态规划
动态规划是一种决策性的问题.... 是在状态中做最优决策的一种特殊的递推算法....
此处先通过一道和上述递推问题及其类似的一道题目上手分析.. 最后得出讨论
746. 使用最小花费爬楼梯
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
竟然动态规划是一种特殊的递推问题, 自然肯定是存在状态定义的, 状态定义是解决动态规划的核心, 状态定义定义的好, 会使得动态规划的状态转移方程简单许多... (后序会一一解释)
定义状态: dp[i] : 爬上 i 阶台阶所需的最小花费
状态转移分析:
initial : dp[0] = 0; dp[1] = 0; 起始楼梯, 没有花销:
class Solution { public: int minCostClimbingStairs(vector<int>& cost) { int n = cost.size(); int dp[n + 1]; //init dp[0] = 0; dp[1] = 0; for (int i = 2; i <= n; ++i) { dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); //决策 } return dp[n]; } };
总结动态规划套路分析:
- 状态定义: dp[i] 符号表达式， 加上含义解释
- 状态转移方程确定. (状态决策过程) 决策最优
- init: 初始化最初状态
- 数学归纳法判断转移方程是否正确, （初学鸡肋, 高手有用, 检查）
三. 动态规划继续研究状态定义和状态转移，通过题目去看看定义和转移过程, 顺便引出状态树。。。。
剑指 Offer II 100. 三角形中最小路径之和
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
图解思路:
- init : dp[0][0] = cost[0][0];
- 转移方程 : dp[i][j] = min(dp[i - 1][j] + cost[i][j], dp[i - 1][j - 1] + cost[i][j]);
class Solution { public: int minimumTotal(vector<vector<int>>& cost) { int n = cost.size(); int dp[n][n]; //init dp[0][0] = cost[0][0]; for (int i = 1; i < n; ++i) { //行 for (int j = 0; j <= i; ++j) { if (j == 0) dp[i][j] = dp[i - 1][j] + cost[i][j]; else if (j == i) dp[i][j] = dp[i - 1][j - 1] + cost[i][j]; else { dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1] ) + cost[i][j]; //状态抉择 } } } int ans = 0x3f3f3f3f; for (int i = 0; i < n; ++i) { ans = min(ans, dp[n - 1][i]); //从最下面一层中抉择结果 } return ans; } };
状态从新定义: 看看状态定义好的优势所在:
dp[i][j] : 从最下面一层到 (i, j) 点的 最短路劲和
init : dp[n - 1][i] : 最下面一层的所有点
转移方程: dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + cost[i][j];
上述定义优势总结: 逆向的定义, 正向走和逆向走其实路劲长度是一致的, 但是排除了特殊情况的判断了
class Solution { public: int minimumTotal(vector<vector<int>>& cost) { int n = cost.size(); int dp[n][n]; //init for (int i = 0; i < n; ++i) { dp[n - 1][i] = cost[n - 1][i]; } for (int i = n - 2; i >= 0; --i) { for (int j = 0; j <= i; ++j) { dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + cost[i][j]; } } return dp[0][0]; } };
三. 再来几道状态定义的练习
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
状态定义： dp[i] : 偷窃前面 i 间屋子且 没有偷相邻物资可以偷窃的最大金额
上述状态定义正确吗???????? 是否存在信息不足????? 还有一个限制, 相邻的物资不可以偷. 所以偷 第 i 间和 没偷 第 i 间是两个状态。。。。 （状态定义核心关键2: 包含所有状态）
dp[i][j] (j = 0 或者1 ): dp[i][0] : 代表不偷 第 i 间屋子可以获取的最大金额, dp[i][1] : 表示偷窃 第 i 间屋子可以获取的最大金额
状态转移: dp[i][0] = max(dp[i - 1][1], dp[i - 1][0]); 不偷第 i 间屋子 就可以偷第 i - 1间屋子, (注意：是可以)
dp[i][1] = dp[i - 1][0] + nums[i - 1] 偷 第 i 间屋子的最大金额, 只能从 dp[i - 1][0] 转移过来， 因为偷了 第 i 间屋子, 则 第 i - 1 间屋子一定是没有被偷的状态 (不能同时偷连续的房子，会报警)
class Solution { public: int rob(vector<int>& nums) { //状态定义: 还是思考最重要的问题?? 状态如何定义????? // dp[i] ???? 足够吗?? 我们尝试一下定义: 前i家物资 最后第i 家偷盗的最大偷盗金额?? // 好像不够呀: 因为 这个转移可能是从 前面的 i - 1 不偷转移过来. 也可以是 i - 1偷转移过来. 这样一分析: 中间还需要保存 不偷的结果呀: //所以这样一想还是需要二维的定义: //dp[i][0] dp[i][1] 就是前面的i个房间 第 i 个房间 不偷和偷的最大偷盗金额 int n = nums.size(); int dp[n + 1][2]; dp[0][0] = dp[0][1] = 0; //没有房间一定是0结果 init for (int i = 1; i <= n; ++i) { dp[i][0] = max(dp[i - 1][1], dp[i - 1][0]); dp[i][1] = dp[i - 1][0] + nums[i - 1]; //只能是前一个房子不偷 } return max(dp[n][0], dp[n][1]); } };
53. 最大子数组和剑指 Offer II 091. 粉刷房子
假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。
例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。
请计算出粉刷完所有房子最少的花费成本。
状态定义: 和上一题一样, 核心关键， 状态定义需要包含所有情况, 染不同的颜色就是不同的状态, 所以需要一个二维数组, 第二维度标识颜色
dp[i][j] (j = 0, 1, 2) : 含义, 前 i 间屋子, 最后第 i 间 屋子 染成 j 颜色所需要的最小花费
状态转移: 核心关键, 最后 的 i 染的颜色 i - 1 不可以染, 所以 dp[i][j] 依赖的是前面的dp[i - 1][k] ( k != j)
上述还是比较抽象， 接下来看代码就好懂了:
class Solution { public: int minCost(vector<vector<int>>& costs) { //定义状态: dp[i][j] : 前 i 个房子 最后一个粉刷 j 颜色的最小花费 //依赖关系: dp[i][j]----> dp[i - 1][k] k != j int n = costs.size(); int dp[n + 1][3]; for (int i = 0; i < 3; ++i) { //init没有一栋屋子染色 dp[0][i] = 0; } for (int i = 1; i <= n; ++i) { //枚举屋子进行状态决策 dp[i][0] = min(dp[i - 1][1] + costs[i - 1][1], dp[i - 1][2] + costs[i - 1][2]); dp[i][1] = min(dp[i - 1][0] + costs[i - 1][0], dp[i - 1][2] + costs[i - 1][2]); dp[i][2] = min(dp[i - 1][1] + costs[i - 1][1], dp[i - 1][0] + costs[i - 1][0]); } return min(dp[n][0], min(dp[n][1], dp[n][2])); } };
53. 最大子数组和
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
状态定义: dp[i] : 到 下标 i 为止的子数组的和的最大值
状态转移: 要么连续 要么断开从新开始..... (连续子数组最大, 只要连续子数组还没成为负数, 就还有可以继续连续, 因为未变成负数之前都可以为后序连续数组变大提供贡献, 除非 < 0 就可以断开了, 要上你只能使得整体变小 品一品这句话的意思, )
依赖状态: dp[i - 1];
状态转移方程: dp[i] = max(dp[i - 1] + nums[i], nums[i]);
class Solution { public: int maxSubArray(vector<int>& nums) { int n = nums.size(); int dp[n]; dp[0] = nums[0];//init int ans = dp[0]; for (int i = 1; i < n; ++i) { dp[i] = max(dp[i - 1] + nums[i], nums[i]);//状态抉择, 连续或者断开 ans = max(ans, dp[i]); } return ans; } };
152. 乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
状态定义: dp[i][0] 和 dp[i][1] : 分别保存前i 个元组的子数组最小和最大乘积
状态转移方程分析: 因为可能存在一个非常小的负数 * 一个负数让整个连续的子数组乘积变得非常大, 所以我们在整个过程中需要保存最大的连续子数组乘积 同时也需要保存最小的连续子数组的乘积, 所以搞出来一个二维数组, 一维保存最小乘积, 另外一位保存最大乘积
依赖状态: dp[i][0] 和 dp[i][1] 都是依赖: dp[i - 1][0] dp[i - 1][1] nums[i - 1]的
接下来的最大值和最小值从: dp[i - 1][0] * nums[i - 1] , dp[i - 1][1] * nums[i - 1] 以及 nums[i - 1] 三者中选择, nums[i - 1] 代表断开前面的乘积, 从新开始
class Solution { //至于这个题目: 首先还是状态定义: //首先: 这个题目: 我们首先分析： 存在 一个负数 * 负变的非常大, 所以一定保存两个状态: //最小值状态 + 最大值状态: //dp[i][0] 和 dp[i][1] 定义: 前面的i个元素的子数组的最小最大乘积 public: int maxProduct(vector<int>& nums) { int n = nums.size(); int dp[n + 1][2]; dp[0][0] = 1, dp[0][1] = 1; //init int ans = INT_MIN; for (int i = 1; i <= n; ++i) { dp[i][0] = min(dp[i - 1][1] * nums[i - 1], dp[i - 1][0] * nums[i - 1]); dp[i][0] = min(dp[i][0], nums[i - 1]); //代表断开 dp[i][1] = max(dp[i - 1][1] * nums[i - 1], dp[i - 1][0] * nums[i - 1]); dp[i][1] = max(dp[i][1], nums[i - 1]); //代表断开 ans = max(dp[i][1], ans); //ans可能是在中间产生 } return ans; //最后返回这个最大值就是 } };
四. 总结:
本章通过区分递推算法 和 动态规划 切入, 引出动态规划的本质和 递推算法不同, 动态规划本质上是一种决策性算法, 是需要做决策获取最优解的算法
然后是抓住动态规划算法的核心, 状态定义, 明确状态定义, 时刻认清状态的含义, 进而通过题目含义 结合状态定义 得出 状态转移方程 (做决策) 然后注意init 和 边界.
状态定义一定包含所有状态, 题目中 或多或少 都会暗示状态的定义, 相邻屋子不可以偷, 就有偷或不偷两个状态, 相邻屋子染色不同, 就有屋子染什么颜色的不同状态
下一章 继续 动态规划算法的优化 , 主要是空间优化, 空间压缩的技巧 + 三种经典背包问题的处理，加刷题
