Java DP Solution


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

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


@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/verysimplejavasolutionwithdetailexplanation/2) and then go back to see LinfinityLab's solution. It totally make sense!!!