Понимание базового варианта в динамическом программировании

Question

Рассмотрим этот вопрос количество различных способов выразить-n сумма-1-3-4

Я понимаю, что f (n) - это число способов представить n в виде суммы1, 3 и 4

f (n-1) - количество способов представить n-1 как сумму 1, 3 и 4

f (1) - количество способов выразить1 как сумма 1, 3 и 4

f (0) - это число способов выразить 0 как сумму 1, 3 и 4

, не должно ли это быть 0, поскольку нет способапредставить / выразить 0 как сумму 1,3,4

Просто начинаю изучать динамическое программирование, но я не понимаю, почему это должно быть 1, а не 0

Answer 1

Ну, допустим, вы хотите представить некоторую сумму S как сумму 1, 3 и 4

Вы можете записать это математически в виде уравнения S = 1*x + 3*y + 4*z, где x, y, z обозначает количество единиц, троек ичетыре в сумме.

Так что теперь f(S) - это просто количество решений уравнения (учитывая, что x, y, z - неотрицательные целые числа)

И когда S=0 мы легко видим, что уравнение имеет одно решение - x=0, y=0, z=0

Answer 2

Если то, что вы предлагаете, было правильным, то мы также не могли бы посчитать 1 + 1 + 1 как способ выразить 3, поскольку эта сумма не включает ни 3, ни 4.

Вместоколичество способов «выразить n как сумму 1, 3 и 4», думать о нем как о количестве вариантов необязательного выбора 1, 3 и 4, которые суммируют с n. Тогда существует только одна такая договоренность для цели 0, которая состоит в том, чтобы выбрать ни одну.