本帖最后由 Rdev 于 2023-3-17 15:03 编辑
爬楼梯（动态规划）
先看下题目要求：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1： 输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
示例 2： 输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶 题目看起来很简单，但是如果没有学过动态规划，可能会没什么思路。
看下题干的示例，我们可以理解为：想要到达N层，那么需要第N-1层的方法加上N-2层的方法，N要大于等于3。
其实这就是动态规划的核心理念，我从某度百科摘抄了下动态规划的描述：
在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线．这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策问题。在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化的过程为动态规划方法。
从上面的摘抄就可知道，所谓动态规划，其实就是：
把问题分解成一步一步的小问题，然后每一步，都依赖于上一步的结果，把上一步的结果当作下一步的「入参」，然后进行一定的策略实现，最后通过合理的策略求得整个问题的最优解。
这里有值得注意的两点，分别是：
1、把大问题分解成小问题。
2、一定的策略，这个策略可以在每一步都不一样，都是可选择的最优策略。
那么，代入题目中，这两点分别就是：
1、把爬多少台阶分解成爬 1 个台阶和爬 2 个台阶这个小问题。
2、策略就是，第 N 个台阶就是第 N-1 个台阶 + 第N-2个台阶的步数之和。
ok，有了这两个思路，那么就可以进行代码整理了。
[Java] 纯文本查看 复制代码 class Solution {
public int climbStairs(int n) {
if(n == 1){
return 1;
}
if(n == 2){
return 2;
}
int r1 = 1,r2 = 2, temp;
for(int i=3;i<=n;i++){
// 注意这里从3开始，因为1和2已经在前面过滤掉了
temp = r1;
// 把r2赋给r1，就是每次循环都是以之前的高值当作低点来计算，每次的步长只有1
r1 = r2;
// 把刚才缓存的 r1 + 刚才的高点r2(就是现在的r1)，加起来，就得到新的高点 r2，
// 这一步也就是这个动态规划的策略。
r2 = r1+temp;
}
return r2;
}
}
好了，当脑海里有过动态规划的思路后，其实代码写起来也是比较简单的，无非就是记住两点：
分解后的小问题是什么？
每一步的策略是什么？
以后遇到类似的后面的值需要以前面的结果为输入的题时，只需要谨记这两点，那么动态规划的题基本是都想得七七八八了，剩下的就是靠练习了。 | 
发表于 2023-3-17 15:00
|
发表于 2023-5-19 15:34
