牛妹上班 题解

简单的不能再简单的动态规划(递推) =。=

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];
    }
};
全部评论

相关推荐

点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务