DP——动态规划入门级教学，什么问题用DP，怎么用DP，三个简单题目帮你理清思路，建立简单DP模板，包教包会

一、DP是什么

动态规划（Dynamic Programming，DP）在算法题中超级常用的一个解题思路

• 目的是求解决策过程最优化，避免重复计算浪费时间
• DP问题的两个特点：最优子问题，重复子问题
• 过程：定义最优解 - 构造最优结构 - 自底向上计算子问题 - 得出结果

二、三个小例子（全是easy题）

2.1 力扣题 70. 爬楼梯的方法

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。
你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

先来定义解是什么：很明显，要到第n层（顶层），可以从n-1层，也可以从n-2层出发，即第n层走法等于前两层走法之和。

解的结构如下：count[n]表示到第n层的走法

count[n]=count[n-1]+count[n-2];

如果按照普通的方法，采用递归实现方法如下：

//获取第i层的走法
public int getCount(int i){if(i==0)return 1;if(i==1)return 1;//count[i]=count[i-1]+count[i-2]return getCount(i-1)+getCount(i-2);
}

这里的i=0取1不代表到0层走法为1，而是从0层到达任意目标的走法，即count[2]=count[1]+count[0]这里的count[0]代表0到第二次层的走法为1（众所周知，0和1需要特殊考虑）。

这里重复计算了count[2]，在更大的数量级上会显著浪费时间。

于是这里应该采用能够利用先前计算结果的，自底向上的动态递归算法

public int getAnswer(int n){if(n==1)return 1;//从0到n层,将每层走法都记录下来（dp数组保存状态）int[] count=new int[n+1];//初始化已知状态count[0]=1;count[1]=1;//自底向上求解for(int i=2;i<=n;i++){//相同解结构count[i]=count[i-1]+count[i-2];}//输出顶层return count[n];
}
//为了节约空间，也可以只保存下一层计算需要的前两层结果，不赘述

2.2 剑指 Offer II 088. 爬楼梯的最少成本

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当爬上一个阶梯都要花费对应的体力值，一旦支付了相应的体力值，就可以选择向上爬一个阶梯或者爬两个阶梯。

请找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

继承上一道题的思路，利用costMin[i]表示到第i层的最低花费，最优解结构如下：

costMin[n]=Math.min(costMin[n-1]+cost[n-1] , costMin[n-2]+cost[n-2]);//再回顾一下上一道题的解结构，发现都利用了n-1，n-2的结果
count[n]=count[n-1]+count[n-2];

于是同样利用相同的模板，运用动态规划算法：
特别注意：这里给出每层花费，需要到达cost.length层

public int getAnswer(int[] cost){int n=cost.length;//n为阶梯数，需要到达第n层//可以直接从0、1层出发，特别考虑到0、1最低花费为0//至少有0层起步花费，即至少有一个cost[0]if(n==1)return 0;//从0到n层,将每层最低花费都记录下来（dp数组保存状态）int[] costMin=new int[n+1];//初始化已知状态costMin[0]=0;costMin[1]=0;//自底向上求解for(int i=2;i<=n;i++){//相同解结构costMin[i]=Math.min(costMin[i-1]+cost[i-1] , costMin[i-2]+cost[i-2]);}//输出顶层return count[n];
}
//为了节约空间，也可以只保存下一层计算需要的前两层结果，不赘述

2.3 力扣题 53. 最大连续子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。

这个问题比上一个问题复杂一点，先给出一个子问题，求出以nums[i]为右端点的最大子数组和，计为childMax[i]。总问题就是max{ childMax[0] , childMax[1] , … , childMax[n-1] }

即解结构如下：

answer=Math.max{childMax[0],childMax[1],...,childMax[n-1]}

具体实现如下，目前还是一个递归的形式：

private int[] nums;public int getAnswer(int n){for(int i=0;i<n;i++){int childMax=getChildMax(i);if(answer<childMax){answer=childMax;}}return answer;
}
//getChildMax()在下面分析
public int getChildMax(int i){if(i==0){return nums[0];return Math.max{getChildMax(i-1)+nums[i],nums[i]};
}

子问题有如下最优解:

//关于i端点独立成一个序列，还是和前面i-1端点合并成一个序列
if(childMax[i-1]>0)childMax[i]=childMax[i-1]+nums[i];
elsechildMax[i]=nums[i];//等价于
childMax[i]=Math.max(childMax[i-1]+nums[i] , nums[i]);
//同上面两道题的形式

于是子问题用递归实现，每次得到子问题的解，比较更新当前答案：

public int getAnswer(int[] nums){int answer=nums[0];int length=nums.length;//dp数组保存状态int[] childMax=new int[length];//初始化已知状态childMax[0]=nums[0];//自底向上求解for(int i=1;i<length;i++){//相同解结构childMax[i]=Math.max(childMax[i-1]+nums[i] , nums[i]);//更新answerif(answer<childMax[i])answer=childMax[i];}//输出需要的dp状态return answer;
}

三、DP分析思路和模板

3.1分析思路：

1. 首先判断问题能不能分为子问题
2. 是否有answer[n] = someFunction ( answer[n-1] … ) 这种形式，能够利用子问题的结果
3. 构建自底向上的方法，求解

3.2 简单DP模板

public int getAnswer(int n){int[] dp=new int[n];//用dp数组保存阶段状态dp[0]=0;//初始化一个dp状态，很容易推断出来的或已知的//自底向上计算for(int i=0;i<n;i++)//相同的解结构dp[i]=someFunction(dp[i-1]);//返回需要的dp结果return dp[n-1];

结尾

关注作者，带你刷题，从简单的算法题了解最常用的算法技能（算法题解双日一更）
每日同类型两道算法题——简单到进阶，让你不知不觉成为无情的刷题机器
如有缺漏，敬请批评指正

题目来源：力扣（LeetCode） 链接：https://leetcode-cn.com/tag/dynamic-programming/problemset/
现在快去把力扣 动态规划的简单题 都刷一遍吧
特别注意：LCP 07.传递信息（这个有点难，好像不是DP问题)