Daily Archives: August 22, 2020

Solution 1, just like frog jump.

public static int minDays(int n) {
    int[] dp = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for (int i = 0; i <= n; i++) {
        if (i * 2 <= n) {
            dp[i * 2] = Math.min(dp[i * 2], dp[i] + 1);
        }
        if (i * 3 <= n) {
            dp[i * 3] = Math.min(dp[i * 3], dp[i] + 1);
        }
        if (i + 1 <= n) {
            dp[i + 1] = Math.min(dp[i + 1], dp[i] + 1);
        }
    }
    return dp[n];
}

Solution 2, don’t consider 1 step away. Only consider n%2, and n%3. Greedy.

public static int minDays(int n) {
    Map<Integer, Integer> dp = new HashMap();
    return helper(n, dp);
}

private static int helper(int n, Map<Integer, Integer> dp) {
    if (n <= 2) {
        return n;
    }
    if (dp.containsKey(n)) {
        return dp.get(n);
    }
    int ans = 1 + Math.min(n % 2 + helper(n / 2, dp), n % 3 + helper(n / 3, dp));
    dp.put(n, ans);
    return ans;
}