Имея число n, мы можем разделить его только на три частиn/2, n/3 и n/4(мы будем рассматривать только целые числа часть). Задача состоит в том, чтобы найти максимальную сумму, которую мы можем получить, разделив число на три части рекурсивно и просуммировав их вместе.
Примечание: Иногда максимальную сумму можно получить, не деля n.
начните с минимального решения n=0, затем maxsum=0, теперь n=1, maxsum=1 и так далее. поэтому мы находим рекурсивное решение типа max(n//2+n//3+n//4,n).
def
solution(n):
dp =
[0 for i in range(n+1)]
dp[0] =
0
dp[1] =
1
for
i in
range(2, n+1):
dp[i] =
max(dp[int(i/2)] +
dp[int(i/3)] +
dp[int(i/4)], i);
return
dp[n]