每天按固定比例吃蛋糕
牛妹的蛋糕
http://www.nowcoder.com/questionTerminal/1f7280d9897d4305b2da6790fe131729
一、思路
用一个数组dp表示当前这天没吃蛋糕之前的蛋糕数目，那么dp的最后一个值，dp[n-1]一定是初始化为1，dp[i]由dp[i+1]推导而来：
因为:
dp[i+1] = dp[i] * (2/3) - 1
所以：
dp[i] = 3*(dp[i+1] + 1)/2
二、图示
三、详细流程
1、特殊情况：n < 1时直接返回0；
2、初始化dp[n-1] = 1;
3、确认循环范围，根据上述公式循环更新dp[n-2] ~ dp[0];
4、返回dp[0]
四、代码
class Solution {
public:
/**
*
* @param n int整型 只剩下一只蛋糕的时候是在第n天发生的．
* @return int整型
*/
int cakeNumber(int n) {
// write code here
if(n < 1)
return 0;
int* dp = new int[n];
dp[n - 1] = 1; //初始化
for (int i = n - 2; i >= 0; --i) {
dp[i] = 3 * (dp[i+1] + 1) / 2;
}
return dp[0];
}
}; 