DP Problem

sohesh doshi
1 min readJan 4, 2020

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]