задача о размене монет (Coin change problem)

Здравствуйте, на Hackerrank решил задачу о размене монет с использованием мемоизации. Однако, мне моё решение, кажется не очень оптимальным. Как его можно улучшить?

Условие.

public static long GetWays(int units, int[] coins, Dictionary<string, long> mem)
    {
        if (units < 0 || coins.Length == 0) return 0;
        if (units == 0) return 1;

        var newCoins = new int[coins.Length - 1];
        Array.Copy(coins, 1, newCoins, 0, coins.Length - 1);
        var coinsStr = string.Join(",", coins) + units;
        var newCoinsStr = string.Join(",", newCoins) + units;
        var newUnitStr = string.Join(",", coins) + (units - coins[0]);
        long answer = 0;
        if (mem.ContainsKey(newCoinsStr)) answer += mem[newCoinsStr];
        else answer += GetWays(units, newCoins, mem);
        if (mem.ContainsKey(newUnitStr)) answer += mem[newUnitStr];
        else answer += GetWays(units - coins[0], coins, mem);
        if (!mem.ContainsKey(coinsStr)) mem.Add(coinsStr, answer);
        return answer;
    }

И еще один вопрос. Я на самом деле не очень понимаю, почему число способов разменять сумму s равно числу способов разменять s с использованием n-1 типом монет + числу способов разменять сумму s - w с использование всех n типов монет. w - достоинство исключенной. Спасибо.

upd. странно, что ссылка не работает. Вставил скриншот условия, дабыл не перепечатывать.