题解 | #牛妹的蛋糕#

思路：

题目的主要信息：

每天吃掉蛋糕总数的1/3，再额外吃1个
吃到第n天还剩下1个蛋糕，问最开始总共有多少蛋糕

这是一个数学问题，可以用递归、动态规划、迭代处理。

方法一：递归
具体做法：
第n天还剩下1一个蛋糕，那么总蛋糕数就是n-1的子问题+1的3/2，可以写出如下递归：

class Solution {
public:
    int cakeNumber(int n) {
        if(n == 1)  //1和2单独讨论
            return 1;
        if(n == 2)
            return 3;
        return 3 * (cakeNumber(n - 1) + 1) / 2; //返回子问题+1的3/2
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，递推公式： $T(n)=T(n-1)+1$
空间复杂度： $O(n)$ ，最大递归树的深度为 $O(n)$

方法二：动态规划
具体做法：
用递归解决的问题，我们也可以用动态规划。借助辅助数组， $dp[i]$ 表示第 $i$ 天吃完后还剩余多少蛋糕， $dp[n - 1] = 1$ ，借助方法一递归的公式往前计算即可。
图片说明

class Solution {
public:
    int cakeNumber(int n) {
        vector<int> dp(n, 0); //dp[i]表示第i天吃完后还剩余多少蛋糕
        dp[n - 1] = 1;//第n天刚好要吃的时候剩余1，即n-1天吃完后为1
        for(int i = n - 2; i >=0; i--)
            dp[i] = 3 * (dp[i + 1] + 1) / 2;
        return dp[0]; //第0天吃完还剩余多少即没吃的时候总数为多少
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，一次遍历
空间复杂度： $O(n)$ ，辅助数组dp的空间

方法三：迭代
具体做法：
仔细观察方法二的动态规划，每次 $dp[i]$ 只用到了 $dp[i+1]$ 的数据，然后依次往前遍历。因此我们可以用一个常量代替数组，每次只需要更新常量即可。

class Solution {
public:
    int cakeNumber(int n) {
        int res = 1;
        for(int i = n - 2; i >=0; i--)
            res = 3 * (res + 1) / 2; //公式并更新res
        return res; 
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，一次遍历
空间复杂度： $O(1)$ ，常数个变量