题意

一个值操作n次

每次对一个值减少它的三分之一向下取整再减1

问 最终剩余1，初始值是多少

题解

根据样例，最大只有10，所以我们不妨来直接正向模拟

1. 10
2. 10-3-1 = 6
3. 6-2-1 = 3
4. 3-1-1 = 1

把这个数据倒过来看

我们发现题意的解其实不唯一，似乎是让我们求最大的

而，从数学上对其反向操作，即是，每次加1，然后乘上二分之三向下取整即可

把数学变成代码

代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 只剩下一只蛋糕的时候是在第n天发生的．
# @return int整型
#
class Solution:
    def cakeNumber(self , n ):
        v = 1
        for i in range(1,n):
            v+=1
            v*=3
            v//=2
        return v

复杂度分析

时间复杂度: 我们执行了n次逆向操作,$O\left(n\right)O(n)$O(n)

空间复杂度: 我们只用了常数个额外变量，因此复杂度为$O\left(1\right)O(1)$O(1)

打表

代码

因为数据范围实在太小，我们可以尝试所有值把答案记录下来，在求答案时直接返回。

class Solution:
    def cakeNumber(self , n ):
        return [0,
                1,
                3,
                6,
                10,
                16,
                25,
                39,
                60,
                91,
                138,
                208,
                313,
                471,
                708,
                1063,
                1596,
                2395,
                3594,
                5392,
                8089,
                12135,
                18204,
                27307,
                40962,
                61444,
                92167,
                138252,
                207379,
                311070][n]

复杂度分析

时间复杂度: 我们直接从表中读取数据，$O\left(1\right)O(1)$O(1)

空间复杂度: 我们用了表来保存答案，因此复杂度为$O\left(n\right)O(n)$O(n)

正向枚举

假设我们 没有找到这个反向计算的公式，那么我们可以通过逐个尝试数值，找到正向计算后能得到同样结果的值。并且根据题意，需要是最大的一个

代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 只剩下一只蛋糕的时候是在第n天发生的．
# @return int整型
#
class Solution:
    
    def daycount(self, v): # 按照题意的正向计算
        cnt = 1
        while v > 1:
            v -= v//3+1;
            cnt +=1
        return cnt
    
    def cakeNumber(self , n ):
        ans = 2;
        while self.daycount(ans) <= n: # 逐个枚举找到合法的最大值
            ans += 1
        return ans - 1

复杂度分析

时间复杂度: 我们需要枚举从1开始到答案为止,所以时间复杂度为$O\left(max\right(ans\left)\right)O(max(ans))$O(max(ans))

空间复杂度: 我们仅用了临时变量和非递归函数，常数大小的空间，因此复杂度为$O\left(1\right)O(1)$O(1)