[数据结构与算法]动态规划——爬楼梯

?用滚动数组的思想。

滚动数组是一种能够在动态规划中降低空间复杂度的方法。有时某些二维dp方程可以直接降阶到一维，在某些题目中甚至可以降低时间复杂度，是一种极为巧妙的思想。

简要来说就是通过观察dp方程来判断需要使用哪些数据，可以抛弃哪些数据，一旦找到关系，就可以用新的数据不断覆盖旧的数据量来减少空间的使用。

例如此题，每次只需保留前两个。

class Solution {
    public int climbStairs(int n) {
        int p=0,q=0,r=1;
        for(int i=0;i<n;i++){
            p=q;
            q=r;
            r=p+q;
        }
        return r;
    }
}

?

?

?