Minimum Cost for n Characters

Problem Overview

You start from zero characters and want exactly n copies of the same letter.

Intuition

You start from zero characters and want exactly n copies of the same letter. Each step you may insert one character for cost i, delete the last character for cost d, or copy everything on screen for cost c (doubling the length). The cheapest way to reach length x is either grow one by one from x-1, or build half (or nearly half) and copy, paying extra insert or delete when the copy overshoots on odd lengths.

Algorithm

1Let dp[0] = 0 and dp[x] = infinity for x > 0.
2For x from 1 to n: set dp[x] = dp[x-1] + i.
3If x is even: also try dp[x/2] + c.
4If x is odd: also try dp[x/2] + c + i (copy floor half then insert one) and dp[x/2 + 1] + c + d (copy ceil half then delete one).
5Return dp[n].

Example Walkthrough

Input: n = 9, insert = 1, delete = 2, copy = 1

1. Build 4 with cost 4, copy to 8 with +1, insert once to reach 9.
2. That beats inserting all nine characters one by one.

Output: 5

Common Pitfalls

• Copy doubles the current string length. You cannot copy from a non-integer half without building it first.
• Odd lengths need both floor-half plus insert and ceil-half plus delete options.
• Deleting costs d, not i. Do not model delete as another insert.
• dp needs size n+1 because transitions read dp[x/2] and dp[x/2 + 1].

Minimum Cost for n Characters.java

Java

// Approach: dp[x] = min cost to build x identical characters. Extend by one
// (dp[x-1] + i), or copy from half (dp[x/2] + c when even). For odd x, copy
// from floor or ceil half and pay one insert or one delete to fix the length.
// Complexity: O(n) time and O(n) extra space.

class Solution {

    public int minCost(int n, int i, int d, int c) {
        int[] dp = new int[n + 1];
        dp[0] = 0;

        for (int x = 1; x <= n; x++) {
            dp[x] = dp[x - 1] + i;

            if (x % 2 == 0) {
                dp[x] = Math.min(dp[x], dp[x / 2] + c);
            } else {
                dp[x] = Math.min(dp[x], dp[x / 2] + c + i);
                dp[x] = Math.min(dp[x], dp[x / 2 + 1] + c + d);
            }
        }

        return dp[n];
    }
}

Was this solution helpful?