Нужна помощь в понимании алгоритма жесткого обмена монет NP на C#. ⇐ C#

[Anonymous]

В одной из моих классных заметок был вопрос с решением: у Джона есть по две монеты каждой монеты со значениями, основанными на 2, возведенных в степень n, и мы должны помочь ему вычислить количество различных способов, которыми можно представить суммируйте с имеющимися у него монетами. Предоставленное решение вообще не заключалось в поиске комбинаций и поиске ответа каким-то математическим способом, и я изо всех сил пытаюсь понять, как оно вычисляет количество способов представления целевого значения (суммы) с помощью этих монет. Так, например, при заданной сумме входных значений = 6 алгоритм должен вернуть 3. В этом случае для Джона возможны следующие три представления:
{1, 1, 2, 2}, {1, 1, 4} и {2, 4}. Вы можете предположить, что сумма будет от 1 до 1 000 000 000 000 000 000 включительно.
Вот решение:

Код: Выделить всё

public static long Solve(long sum)
{
if (sum \< 0) return 0; // No coins and no sum possible
if (sum is 0) return 1; // Complete combination found

if(!_cache.ContainsKey(sum))
{
if (sum % 2 is 0)
{
_cache.Add(sum, Solve(sum / 2) + Solve(sum / 2 - 1));
}
else
{
_cache.Add(sum, Solve((sum - 1) / 2));
}
}
return Convert.ToInt64(_cache[sum]);
}

Я знаю, что он использует динамическое программирование для хранения возможных комбинаций, и я понимаю эту часть, но я не понимаю, как он обеспечивает получение всех возможных комбинаций с помощью 2 каждой монеты? В чем смысл проверки четности и нечетности? Почему не нужно добавлять результаты, если они нечетные, но необходимо для четных чисел? Я видел этот пост «Двоичное представление», и в нем есть объяснение подобных побитовых операций, которые, как я думал, объясняли, как это работает, но я тоже не понимаю, как оно это делает.
А также эти 2 строки — это основа того, чего я не понимаю, и почему он выполняет sum/2 вместо чего-то вроде Floor(log(sum)), чтобы получить ближайшее значение степени 2.

Код: Выделить всё

_cache.Add(sum, Solve(sum / 2) + Solve(sum / 2 - 1));

Код: Выделить всё

_cache.Add(sum, Solve((sum - 1) / 2));

Я был бы очень признателен, если бы кто-нибудь смог разобраться в логике этого кода и понять, как этот алгоритм подсчитывает количество комбинаций?

Подробнее здесь: https://stackoverflow.com/questions/784 ... in-c-sharp