# Java DP Solution

• @shreydesai Actually, you haven't answered the question proposed by @xuanyue_vol .

• @gerrybio dp[i] should be thought of as sum of all prime factors (counted with multiplicity), then it's clear that it doesn't matter which prime you choose.

For example, dp[20] = 9 because 20 = 2x2x5 and 2+2+5 = 9. It doesn't matter if you calculate this sum as (2+2) + 5 (i.e. dp[4] + 20/4 ) or (2+5) + 2 (i.e. dp[10] + 20/10).

• Like checking Prime numbers, I think for the second loop, you do not need to iterate through i -1 to i `for (int j = i-1; j > 1; j--)`. Alternatively, you can only check i to Math.sqrt(i). It will pass all test cases as well.

• @ho_chung
Thanks a lot! Makes a lot of sense. dp[i] is actually sum of all prime factors! And for prime factors, dp[i] = i !

• @yuxiangmusic I understand this solution, but I just can't figure out why the "d" value should be the one to split instead of the value of n/d.

• @LinfinityLab Please tell me why dp[i] = dp[j]+(i/j), rather dp[i]=dp[i/j]+i, I just can't figure it out.

• @vvvincentvan

dp[i] = dp[j]+(i/j),
dp[i]=dp[i/j]+i

I think these two are equivalent

• @zestypanda I think it is O(n^2). If i is a prime number, the inner loop would run i times.

• @LinfinityLab Any proof of why only highest factor should be considered .
For ex if a,b (the highest div) are divisors of n , How can we say that
d[n] = d[b] + n/b would always be lesser that
d[n] = d[a] + n/a ?

• Very good solution. Initially I don't quite understand the logic behind. However, after I saw the explanation posted here(https://discuss.leetcode.com/topic/97752/very-simple-java-solution-with-detail-explanation/2) and then go back to see LinfinityLab's solution. It totally make sense!!!

• it is so difficult to understand!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.