题目
思路
这题先后做两遍:
第二遍的思路是直接上数学推导。
1 | class Solution { |
而第一遍的做法虽然更符合编程逻辑但是可能计算量更大,思路是对每一天计算当前所属轮次,累积和。但是其实可以用动态规划适当优化,使用一个大小为 n+1
的数组dp[n]
,dp[i]
表示第i
天所属轮次,那么如何判断i-1
天是否是其所属轮次的最后一天呢?如果dp[i-1-dp[i-1]+1] = dp[i-dp[i-1]
与dp[i-1]
属于同一轮次,那么dp[i] = dp[i-1]+1
,否则dp[i] = dp[i-1]
。
1 | class Solution { |