Need help in figuring out bug in Word Wrap problem DP solution

Viewed 23

The problem statement is given here : https://practice.geeksforgeeks.org/problems/word-wrap1646/1#

This it the solution I came up with.

class Solution
{
    public int solveWordWrap (int[] nums, int k)
    {
        return solveWordWrap(0,nums,k);
    }
    
    private int solveWordWrap(int startIndx, int[] nums, int k){
        
        if(startIndx >= nums.length-1)
            return 0;
        
        int min = Integer.MAX_VALUE;
        
        int charCount = 0;
        int words = 0;
        for(int i = startIndx; i < nums.length; i++){
            charCount = charCount + nums[i];
            words++;
            if(charCount+words-1 <= k)
                min = Math.min( (int)Math.pow(k - (charCount+ words-1),2) + solveWordWrap(i+1,nums,k),min);
            else
                break;
        }
        
        return min;
    }
}

For the input

nums = {10,6,5,3,1,10,8,2}
k = 12

The correct solution is 45, but my code is outputting 46.

I am not able to find the error.

0 Answers
Related