how to prove the dp d[I] = d[j] + I / j is correct?


  • -1
    X

    '''public int minSteps(int n) {
    int[] nums = new int[n + 1];
    //nums[0] = 0;
    //nums[1] = 0;

        if(n == 0 || n == 1){
            return 0;
        }
    
        for(int i = 2; i <= n; i++){
            nums[i] = i;
    
            for(int j = i - 1; j > 1; j--){
                if(i % j == 0){
                    nums[i] = Math.min(nums[i], (nums[j] + i / j));
                }
            }
    
        }
    
        return nums[n];
    }'''
    

    So this is a n^2 solution, and we could modify this answer with get the biggest factor and then break. It would got the correct answer either.

    That means '''if i % j == 0; d[I] = d[j] + I / j;''' we get the answer when we get the biggest factor. why? how could I prove it? because d[j] is monotonically increasing but I / j is decreasing....


Log in to reply
 

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