как базовый случай D [0] равен одному, где D [n] - количество способов, которыми n может быть выражено как сумма 1,3,4?

Question

Я пробую задачу на динамической задаче, которая потребовала найти количество способов найти n в сумме 1,3 и 4. я вижу решение на вундеркиндов для гиков.

базовые случаи проблемы были d [0] = d [1] = d [2] = 1

как d [0] = 1, где d [n] - это количество способов выразить d [n] как сумму 1,3,4.

d [0] должно быть равно нулю, поскольку нет возможности выразить 0 как сумму 1,3 и 4.

это ссылка, по которой дается решение. https://www.geeksforgeeks.org/count-ofdifferent-ways-express-n-sum-1-3-4/

Answer 1

Нет возможности выразить 0 как сумму 1,3 и 4

Да, есть. Предполагается, что пустой массив имеет сумму 0. Таким образом, выбор нуля 1 с, нуля 2 с и нуля 3 с является одним из способов получения 0 как суммы 1, 3 и 4.

Answer 2

d [0] должно быть равно нулю, поскольку нет возможности выразить 0 как сумму 1,3 и 4.

Это вопрос того, как вы это определяете. Наиболее удобным определением «суммы 1,3 и 4» является «значение вида a + 3 b + 4 c , где a , b и c являются неотрицательными целыми числами ", а" способ выразить [значение] как сумму 1,3 и 4 "как выбор a , b и c .

Вы, очевидно, изображаете более строгое определение, которое также требует a + b + c ≥ 1; это точно не неправильно , но это дает вам больше особых случаев для обработки в вашем рекурсивном случае. Это упрощает вычисления, если вы пропустите это требование.