You are given an integer n representing a target score.
Your score starts at 0, and each day you either earn points or skip.
Points are earned during a streak. On the first day of a streak you earn 1 point, on the second day 2 points, on the third day 3 points, and so on. Skipping a day earns nothing and resets the streak, so the next time you earn points, you start from 1 again.
Return the minimum number of days, including any skipped days, needed to reach a score of exactly n.
Example 1:
Input: n = 2
Output: 3
Explanation:
n = 2.n = 2 in 3 days.Example 2:
Input: n = 9
Output: 6
Explanation:
1 + 2 + 3 = 6.6 + 1 + 2 = 9 in 6 days.Example 3:
Input: n = 12
Output: 7
Explanation:
1 + 2 + 3 = 6.6 + 1 + 2 + 3 = 12 in 7 days.
Constraints:
1 <= n <= 105class Solution {
public int minDays(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
for (int j = 1; j <= n; j++) {
int sum = 0;
for (int m = 1; (sum += m) <= j; m++) {
if (sum == j) // Compute atomic scores
dp[j] = Math.min(dp[j], m);
else if (dp[j - sum] != Integer.MAX_VALUE) // Compute composite if atomic found
dp[j] = Math.min(dp[j], m + 1 + dp[j - sum]);
}
}
return dp[n];
}
}