Рекурсивный алгоритм Сложность времени: смена монет

Я перебрал некоторые алгоритмы и наткнулся на обмен монет проблема.

Размышляя о проблеме, я придумал это наивное рекурсивное решение:

int coinChange(const vector<int>& coins, int start, int n) {
if (n == 0) return 1;
if (n < 0) return 0;

int total = 0;

for (int i = start; i < coins.size(); ++i) {
if (coins[i] <= n) total += coinChange(coins, i, n-coins[i]);
}

return total;
}

Затем я понял, что «принятое» решение было следующим:

int count( int S[], int m, int n )
{
// If n is 0 then there is 1 solution (do not include any coin)
if (n == 0)
return 1;

// If n is less than 0 then no solution exists
if (n < 0)
return 0;

// If there are no coins and n is greater than 0, then no solution exist
if (m <=0 && n >= 1)
return 0;

// count is sum of solutions (i) including S[m-1] (ii) excluding S[m-1]
return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
}

Сначала я думал, что эти два были по существу одинаковыми. Мне было ясно, что мое дерево рекурсии было намного шире, но казалось, что это было только потому, что мой алгоритм выполнял больше работы на каждом уровне, поэтому он выровнялся. Похоже, что оба алгоритма рассматривают количество способов внесения изменений в текущую монету (учитывая, что это <= текущая сумма), и учитывая количество способов внести изменения без текущей монеты (таким образом, со всеми элементами в массиве монет минус текущая монета). Поэтому параметр start в моем алгоритме делал по существу то же самое, что и m делает во втором алгоритме.

Чем больше я смотрю на это, тем не менее, кажется, что независимо от предыдущего текста, мой алгоритм O(n^n) а второй O(2^n), Я смотрел на это слишком долго, но если бы кто-то мог объяснить, какую дополнительную работу выполняет мой алгоритм по сравнению со вторым, это было бы здорово.

РЕДАКТИРОВАТЬ

Я понимаю динамическое программирование решения этой проблемы, этот вопрос является чисто сложным вопросом.