蓝桥杯备赛leetcode 70.爬楼梯，用最经典的题目来讲解动态规划

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼梯顶部呢？

先看题解，然后我们再来慢慢解释

class Solution {
public:
    int climbStairs(int n) {
        if(n<=2){
            return n;
        }//如果只需要爬到1阶或者二阶，那么我们直接返回n
        int dp[n];//每个动态规划类的题目几乎都要建立dp数组来存放状态
        dp[0] = 1;//建立初始值
        dp[1] = 2;
        for(int i = 2;i<n;i++){
            dp[i] = dp[i-1] + dp[i-2];//dp状态转移式
        }
        return dp[n-1];//返回计算值
    }
};

首先我们来了解一下什么是动态规划思想吧

动态规划是将问题实例分解为一个又一个子问题来求解。

这是大多数博主都在强调的一个思想，但是，这个回答太过官方与死板，让初学者很难理解。

那么怎么样能够让人好懂呢？

我们先来看动态规划题目的解题步骤吧

其一：确定状态

第一步我们需要确定每一步的状态，我们建立一个dp数组，来存放每一个阶梯的状态，每个dp数组的值即最佳状态

这一步实际上说简单也简单，说难也难，不过我这里有一个很好用的土方法，就是自己先把前面数据量小的dp数组手算出来，拿这题举例

我们不知道它的状态转移式时，我们可以先计算前三个或者前四个

得出dp[0] = 1,dp[1] = 2,dp[2] =3,dp[3] = 5,这里这一段我们不明所以也没关系，我们接着看

第二步：确定状态转移式

这是最重要的一步，下面附图

比如说第n阶梯，我想要到达n，那我是不是只能从n-1阶和n-2阶跳上来，那么，如果我的dp[n-1]和dp[n-2]已经记录了到达n-1和n-2的最大方法，而n又只能从n-1或者n-2跳上来，那我们把跳两步和跳一步的情况都加起来了，我们的dp[n]是不是就已经记录了到n阶的最多方法了呢，那我们再看第一步我们推出来的前四个dp数组元素，我们是不是能够得出dp状态转移式了呢

dp[0] = 1;//第一阶梯最优解

dp[1] = 2;//第二阶梯最优解

dp[2] =3;//前两阶梯加起来得出的最优解

dp[3] = 5;//前两阶梯加起来得出的最优解

即dp[i] = dp[i-1] + dp[i-2];

第三步：确立边界和初始值，

dp[0]=1;
dp[1]=2;

这里我们给dp[0]和dp[1]赋一个初值，因为我们的状态转移式并不能得到前两个元素的值，随后我们只要用循环跟着递推式来计算就行了：

for(int i = 2;i<n;i++){
            dp[i] = dp[i-1] + dp[i-2];
        }

随后我们返回dp[n-1]，即我们所要求的爬上台阶的方法数。