@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 = 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 + 20/4 ) or (2+5) + 2 (i.e. dp + 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.
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.
dp[i] = dp[j]+(i/j),
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!!!
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.