开篇
本文可能和你以前所见的直接讲动态转移方程的动态规划文章不同，笔者在学习动态规划期间，也看过很多类似的教程，感觉对于萌新的我一脸蒙蔽，感觉就是像高中数学老师拿着答案给我们讲解一样。
本文按照算法导论的思路由递归演化到动态规划，带你感受其中的优化
开头会说一些常用的动态规划步骤也方便大家一起学习和类比
还有人会说up，up，我会用递归解出来了，还要啥动态规划啊，这不是吃咸鱼蘸酱油 —多此一举吗？
咋要是都能轻松AC，代码优雅，高效，还要啥动态规划啊，
递归代码人偷懒了，关键是费机器，慢，特别容易超时
但是也不是说递归的思想就很简单了，我一直觉得递归几乎可以贯穿所以的算法，而用的好可以用最简单的代码完成任务，因为递归的黑盒特性，这点在二叉树章节想必大家有所体会。
而且对于优化比较好的code面试官也会对你印象深刻些，和其他人有区分度
我觉得在最前面我需要先说一些你从教材和算法导论上的基础概念和思想，
如果你觉得初学无法理解这么多名词那么多总结的思想，可以先跳过，我会在文章的最后再去把贪心，分治，回溯，动态规划这几种算法在放在一起对比一下使用场景
使用动态规划通常用来求解全局的最优解问题，为了求解全局最优解所有很自然的想到计算出所有的解然后返回最优解，而动态规划的核心思想就是 用于子问题重叠的情况，即不同的子问题具有公共的子子问题。动态规划算法对每个子问题只求解一次，将其解保存到一个表格中，避免重复计算，最后将这些子问题组合可以得出一个最优解
一句话总结就是每次计算完只有记录在表中，然后依靠表中的数据进行计算；
大家常见的动态规划步骤
- 1.创建dp 理解其含义
- 2.递推公式 -状态转移方程
- 3.初始化dp数组
- 4.遍历顺序，计算结果
这里的每一步都非常重要，当你做的题够多就明白你出错可能是某一步有问题
这里我们先用一个最简单的爬楼梯问题举例说明各种方法并且逐渐进阶
题目:leetcode 70.爬楼梯
假设你正在爬楼梯，需要n阶才能到达楼顶 ，每次你可以爬1个或者2个台阶，。
返回你有多少种不同的方法爬到楼顶。
本文中的代码你也可以上leetcode去运行
最初始版本 朴素暴力递归尝试-回溯
递归思想其实和回溯思想很像，就是无脑穷举尝试所有值，很好理解,想求解全局最优解必然是穷举所有可能性，然后对比选出最优解
每一个台阶到楼顶的路径数 等于当前位置跳一格加上跳两格的尝试方法数的和
递归三部曲为
- 1.递归的返回值 和 参数列表 //返回值应该是尝试的路径数 ,参数列表是剩余多少爬完
- 2.确定递归的终止条件 //倘若递归计算到，rest等于0步代表爬到楼顶了，返回一种成功的尝试
- 3.递归单层逻辑 每一层都是递归的计算当前层的尝试路径数 等于rest - 1和 rest - 2 的尝试路径数和
class Solution {
public int climbStairs(int n) {
return f(n);
}
public int f(int rest){
//base case 终止条件
if(rest == 0) return 1;
if(rest < 0) return 0;
//每一个台阶到达台阶为方法等于当前位置跳一格加上跳两格的尝试方法数的和
return f(rest -1) + f(rest - 2);
}
}
一棵高度为k的决策树形状为二叉树，每个地方都分出两个选择
时间复杂度 2^K
这个版本虽然比较容易想到，符合人类正常尝试思维，但是非常容易超时,从图中可以看出这个版本在求解子问题的时候充斥着大量的重复计算，
这样可以引出 相同的子问题 我们可以把每次计算的结果记录下来因此引出了备忘录法
记忆化搜索，自顶向下的动态规划—备忘录法
相比普通的递归计算，其实在时间复杂度上已经接近常用的动态规划了，也已经可以AC了
这也算是一种自顶向下的动态规划思路
具体的操作
增加一个备忘录数组dp[n+1] 每次先去检查表是否已经计算过，如果计算过直接返回表中的结果，避免重复计算
class Solution {
public int climbStairs(int n) {
//dp含义 下标表示你还需要走rest步, 数组中元素表示可以到达顶部的路径数
int[] dp = new int[n+1];
//将dp数组都初始化为 -1 用来标记该位置没有计算过
for(int i = 0;i < dp.length; i++){
dp[i] = -1;
}
return F(n,dp);
}
public int F(int rest,int[] dp){
//终止条件
if(rest == 0) return 1;
if(rest < 0) return 0;
//不等于 -1 代表之前计算过直接 return 数组中的结果
if(dp[rest] != -1) return dp[rest];
//等于 -1 代表没有计算过需要计算
//计算之后先要存在备忘录中
dp[rest] = F(rest - 1,dp) + F(rest - 2,dp);
return dp[rest];
}
}
但是该方法还是使用的递归自顶向下的方式计算，而递归会有额外的开销，因此也引出另外一种优化思路，先求解子问题自底向上的求解问题，最后将子问题的解组合起来，
实现的方式就是 通过表数据之间的结构依赖来计算，而这个表结构依赖就是所谓的动态转移方程
自底向上—表结构依赖的动态规划
这一版也需要一个状态记录表，也需要将计算完的结果存到表中 ，和上一般的核心区别在于这里的计算是研究数据之间的表结构依赖关系去计算结果 ，也就是常说的状态转移方程
具体状态转移方程该如何的来呢？ 是你看题直接灵机一现顿悟道法？
动态转移方程的来源 ！！！如果你真的按照本文的思路在思考优化，那么其实动态转移方程也已经从递归的思路中呼之欲出的，动态转移方程就是递归的单层递归逻辑演变而来，
其实基本没有修改，递归版本是将计算结果递归返回给上层的递归调用，然后将这次计算结果记录在备忘录中，而动态规划不过是将结果直接返回到了dp状态表中保存。
在递归备忘录版本中,递归计算完每一个值都会将值记录在dp数组中，假设到最后每一个调用递归的计算需要的数据都保存在了备忘录中，是不是就可以看作只调用表格中的值来计算,用伪代码举个简单的例子
假设求解rest = 5
//递归求解当前值 为跳一步 和 跳两步的 路径数和
clim(5, dp) = clim(4, dp) + clim(3, dp);
//倘如此时clim(4 , dp) + clim(3 , dp) 都已经被计算过了是从备忘录数组中取值,
//并且将clim(5, dp)存入数组中
dp[5] = clim(5, dp) = dp[4] + dp[3];
//看到这里就可以看出动态转移方程了
dp[i] = dp[i - 1] + dp[i - 2];
class Solution {
public int climbStairs(int n) {
//记录你还需要走rest步 可以到达顶部的路径数
int[] dp = new int[n+1];
//将dp数组都初始化为 -1 用来标记该位置没有计算过
for(int i = 0;i < dp.length; i++){
dp[i] = -1;
}
return F(n,dp);
}
public int F(int rest,int[] dp){
if(rest == 0) return 1;
if(rest < 0) return 0;
//不等于 -1 代表之前计算过直接 return 数组中的结果
if(dp[rest] != -1) return dp[rest];
//等于 -1 代表没有计算过需要计算
//计算之后先要存在备忘录中
dp[rest] = F(rest - 1,dp) + F(rest - 2,dp);
return dp[rest];
}
}
不过其实动态转移方程的本质是通过数据之间的表结构依赖关系去计算
这个表结构依赖关系可以由图表轻松看出,可以轻松得到和理解动态转移方程
如果你已经会求解动态转移方程，不过这里其实还有一个问题就是递归是自顶向下去计算也就是我们先计算f（7）的时候再去递归计算f（6）和f（5），在最开始的备忘录数组中是没有数据也可以计算的。
但是在通过动态转移方程，只严格依赖表结构的计算，自底向上的计算，也就是我们先计算得到的dp[1] ,dp[2]，再通过方程计算得出dp[3]，因此最开始表中必须要有基础数据。
由此引出动态规划重要步骤之一：dp数组的初始化
很多人有一个误区认为动态规划难点也就一个动态转移方程了，刷题可能看个动态转移方程一抄就觉得自己ok了，如果还是AC不了，可能就一点一点的 欸 ！模仿，读书人的事情怎么能是抄呢
其实还有一部十分的关键就是关于dp数组的初始化，
相信你看到现在也大致猜到了初始化的思路源于递归的终止条件，也就是最基础的初始化数据。也可以从题意中取提取更多初始化的信息丰富dp基础信息;
核心点 ： 递归的终止条件可以作为初始化的关键信息 类似于斐波那契数列的第零项和第一项dp数组初始化的数据， 本题还可以直接读题意获取初始化信息
public int clim(int rest){
if(rest == 0) return 1;
//越界了
if(rest < 0) return 0;
return clim(rest -1) + clim(rest - 2);
}
其实这里还有重要的一步就是遍历结算的顺序，遍历起点应该是你可以通过初始化的基础数据的方向开始，dp[0],dp[1],dp[2]有初始化数据，所有从前往后遍历
最后这里放下动态规划版本和初始递归版本的对比
class Solution {
public int climbStairs(int n) {
if(n n ){
return 0;
}
//尝试可以走到终点,则尝试路径数加一
if(h == m && l == n) return 1;
//如果在最下面一行只能尝试往右走
else if(h == m){
return process(h,l+1,m,n);
}
//如果在最右边一列只能尝试往下走
else if(l == n){
return process(h+1,l,m,n);
}
//中间的普遍位置尝试路径数为 向下尝试路径数 加上 向右尝试路径数
else { return process(h,l+1,m,n) + process(h+1,l,m,n);}
}
}
用上备忘录以后你就会发现执行时间大大提升了，和常规的动态规划几乎没有差别1，也可以击败100%了
class Solution {
public int uniquePaths(int m, int n) {
if(n < 2 || m< 2 ){
return Math.min(n,m);
}
//dp数组的含义 下标对应当前行，当前列 ，数组元素对应当前位置到终点的路劲数
int[][] dp = new int[m+1][n+1];
//初始化dp 标记为未计算
for(int i = 0; i < m + 1; i++){
for(int j = 0; j m || l > n ){
return 0;
}
if(dp[h][l] != -1) return dp[h][l];
//尝试可以走到终点,则尝试路径数加一
if(h == m && l == n) return 1;
//如果在最下面一行只能尝试往右走
else if(h == m){
dp[h][l] = process(h,l+1,m,n,dp);
return dp[h][l];
}
//如果在最右边一列只能尝试往下走
else if(l == n){
dp[h][l] = process(h+1,l,m,n,dp);
return dp[h][l];
}
//中间的普遍位置尝试路径数为 向下尝试路径数 加上 向右尝试路径数
else {
dp[h][l] = process(h,l+1,m,n,dp) + process(h+1,l,m,n,dp);
return dp[h][l];
}
}
}
dp数组的含义 下标对应当前位置，数组元素对应当前位置到终点的路径数
由递归的尝试思想，观察图,对于一般位置来讲每一个格子可以走的路径数为下一步往 右走 和往下走的路径数和
能够得到状态转移方程 dp[i][j] = dp[i][j+1] + dp[i+1][j]
接下来我们考虑一下初始化以及边界条件
因此最下面一行和最右边一行都应该初始化为1
下一步就是遍历顺序了
结合我们的初始化数据和动态转移方程，这题的遍历顺序应该是从最后一排最后一列往第一排第一列遍历。
class Solution {
public int uniquePaths(int m, int n) {
if(n < 2 || m< 2 ){
return Math.min(n,m);
}
//dp数组的含义 下标对应当前位置，数组元素对应当前位置到终点的路径数
int[][] dp = new int[m+1][n+1];
//初始化dp 由递归关系可以直接求出动态转移方程
dp[m][n] = 1;
for(int i =1 ;i < m; i++){
dp[i][n] = 1;
}
for(int i = 1; i 0;i--){
for(int j = n -1; j > 0; j--){
dp[i][j] = dp[i][j+1] + dp[i+1][j];
}
}
return dp[1][1];
}
}
01背包模型
如果你看完上面的内容已经有所思考那我们就来自己尝试应用在解决背包问题上,
选择背包模型是因为它十分经典，学习规划的第一个遇到的模型基本就是背包模型。
而其实应对大厂面试，背包九讲重点学习 01背包问题和完全背包问题就足够了，其他的背包模型都是竞赛的级别，可以拓展了解但是不是重点
这里的模型是最根本的01背包问题也是最重要的背包模型
题目为：有n件物品和一个最多能背重量为w 的背包。给你一个全部物品重量的数组weight[ ]，第i件物品的重量是weight[i]，物品价值的数组value[ ],得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
这里都为了偷懒把一些应该是输入的参数，写成了全局的变量
public class Demo1 {
static int[] weight = {3, 2, 4, 6, 3}; // 物品的重量
static int[] value = {5, 4, 8, 15, 6}; // 物品的价值
static int n = 5; // 物品个数
static int w = 9; // 背包承受的最大重量
public static void main(String[] args) {
System.out.println( f(0, 0, 0));
}
// i 是当前遍历到第i个物品,curWeight是当前选择物品的总重量 curValue当前选择物品的总价值
public static int f(int i, int curWeight, int curValue) {
// 递归终止条件 curWeight==w表示装满了，i==n表示物品都遍历完了
if (curWeight == w || i == n) {
return curValue;
}
// 在容量足够的情况下，选择 装第i个物品 或者 不装第i个物品 中会导致当前价值最大的选择
if (curWeight + weight[i]
