DP Problem

Given a number n, we can divide it into only three parts n/2, n/3, and n/4 (we will consider only integer part). The task is to find the maximum sum we can make by dividing the number into three parts recursively and summing up them together.
Note: Sometimes, the maximum sum can be obtained by not dividing n.

start with the minimum solution n=0 then max sum=0 now n=1 , maxsum=1 so on. so we find a recursive solution like 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]