# DP Problem

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).

defsolution(n): dp=[0 for i in range(n+1)] dp[0]=0 dp[1]=1foriinrange(2, n+1): dp[i]=max(dp[int(i/2)]+dp[int(i/3)]+dp[int(i/4)], i);returndp[n]