牛妹上班 题解

简单的不能再简单的动态规划（递推） =。=

class Solution {
public:
    /**
     * 
     * @param X int整型 公司所在的台阶
     * @return int整型
     */
    int stepsFunction(int X) {
        // write code here
        int num[40];
        num[0] = 1;
        num[1] = 1;
        num[2] = 1;
        for (int i = 3; i < X; i ++)
            num[i] = num[i-3] + num[i-2];
        return num[X-1];
    }
};

如果非要锦上添花搞一搞，可以状态压缩

class Solution {
public:
    /**
     * 
     * @param X int整型 公司所在的台阶
     * @return int整型
     */
    int stepsFunction(int X) {
        // write code here

        int num[4];
        num[0] = 1;
        num[1] = 1;
        num[2] = 1;
        for (int i = 3; i < X; i ++)
            num[i%4] = num[(i-3)%4] + num[(i-2)%4];
        return num[(X-1)%4];
    }
};