DP——动态规划入门级教学，什么问题用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];
1

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

//获取第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);
}
1
2
3
4
5
6
7
8
9
10
11

这里的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
1
2
3
4
5
6
7
8
9
10
11