题解 | #牛妹的蛋糕#

题目描述
众所周知，牛妹非常喜欢吃蛋糕。
第一天牛妹吃掉蛋糕总数三分之一（向下取整）多一个，第二天又将剩下的蛋糕吃掉三分之一（向下取整）多一个，以后每天吃掉前一天剩下的三分之一（向下取整）多一个，到第n天准备吃的时候只剩下一个蛋糕。
牛妹想知道第一天开始吃的时候蛋糕一共有多少呢？
这道题是典型的猴子吃桃问题，只要明确一点：前一天蛋糕数量为 $x2$ ，后一天蛋糕数量为 $x1$ , $x2-((1/3)x1+1)=1$ $图片说明$ $x2=3*(x1+1)/2$

方法一：迭代法

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

复杂度：
时间复杂度：一层循环，时间复杂度为 $O(n)$
空间复杂度：常数级变量，空间复杂度为 $O(1)$

方法二：递归
递推公式为：
图片说明

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

复杂度：
时间复杂度：递归深度为n，每次递归函数的复杂度为常数级，所以时间复杂度为 $O(n)$
空间复杂度：递归运行时栈的大小不超过n，空间复杂度为 $O(n)$

方法三：动态规划
显然，状态转移方程 $dp[i]=3*(dp[i-1]+1)/2$

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

复杂度：
时间复杂度：遍历一次 $dp$ 数组， $O(n)$
空间复杂度：额外使用 $dp$ 数组的大小为n,空间复杂度为 $O(n)$