题目描述

众所周知，牛妹非常喜欢吃蛋糕。
第一天牛妹吃掉蛋糕总数三分之一（向下取整）多一个，第二天又将剩下的蛋糕吃掉三分之一（向下取整）多一个，以后每天吃掉前一天剩下的三分之一（向下取整）多一个，到第n天准备吃的时候只剩下一个蛋糕。
牛妹想知道第一天开始吃的时候蛋糕一共有多少呢？
主要信息：每天吃蛋糕总数三分之一（向下取整）多一个；第n天只剩1个

方法一 递归

解题思路

设前后两天的蛋糕数为和，根据题意有，那么，已经知道第天的蛋糕数为，所以可以通过递归的方法求得第一天的蛋糕数。

代码示例

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 只剩下一只蛋糕的时候是在第n天发生的．
     * @return int整型
     */
    int cakeNumber(int n) {
        // 边界条件
        if(n == 1)
            return 1;
        if(n == 2)
            return 3;
        // 根据推理所得公式进行迭代
        return 3 * (cakeNumber(n - 1) + 1) / 2;
    }
};

复杂度分析

• 时间复杂度：需要从第天递归到第天，间复杂度为
• 空间复杂度：需要从第天递归到第天，递归栈的深度为，空间复杂度为

方法二 迭代

解题思路

与方法一的思路类似，，为了减少空间复杂度，使用迭代的方法求解。

代码示例

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 只剩下一只蛋糕的时候是在第n天发生的．
     * @return int整型
     */
    int cakeNumber(int n) {
        int res = 1;
        for(int i = n - 2; i >= 0; i--)
            // 根据公式更新res
            res = 3 * (res + 1) / 2;
        return res;
    }
};

复杂度分析

• 时间复杂度：需要从第天模拟到第天，间复杂度为
• 空间复杂度：使用了常数个变量，空间复杂度为