Rod cutting problem

make cuts of rod and return highest value

Given a rod of length N inches and an array price[] where price[i] denotes the value of a piece of rod of length i inches (1-based indexing). Determine the maximum value obtainable by cutting up the rod and selling the pieces. Make any number of cuts, or none at all, and sell the resulting pieces.

Example 1: Input: price = [1, 6, 8, 9, 10, 19, 7, 20], N = 8

Output: 25

Explanation: Cut the rod into lengths of 2 and 6 for a total price of 6 + 19= 25.

Example 2: Input: price = [1, 5, 8, 9], N = 4

Output: 10

Explanation: Cut the rod into lengths of 2 and 2 for a total price of 5 + 5 = 10.

Solution

here index+1 would be length of piece, so index 0 would be length 1

RodCutting(price, n) {
   let dp = Array.from({ length: n }, () => Array(n + 1).fill(-1));
   function recurr(index, length) {
     if (index === 0) {
       return length * price[0];
     }

     if (dp[index][length] !== -1) {
       return dp[index][length];
     }

     let notTake = recurr(index - 1, length);

     let take = -Infinity;

     let pieceLength = index + 1;

     if (pieceLength <= length) {
       take = price[index] + recurr(index, length - pieceLength);
     }

     dp[index][length] = Math.max(take, notTake);
     return Math.max(take, notTake);
   }

   return recurr(n - 1, n);
 }

Tabulation

 cutRod(price, n) {
        // One cell represents an item-length state.
        const dp = Array.from(
            {length: n},
            () => new Array(n + 1).fill(0)
        );
 
        // The base row uses only length-one pieces.
        for (let rodLength = 0;
             rodLength <= n;
             rodLength++) {
            dp[0][rodLength] = rodLength * price[0];
        }
 
        // Each pass introduces one longer piece.
        for (let index = 1; index < n; index++) {
            const pieceLength = index + 1;
 
            // Ascending lengths allow repeated pieces.
            for (let rodLength = 0;
                 rodLength <= n;
                 rodLength++) {
                // The previous row supplies the skip value.
                const notTake =
                    dp[index - 1][rodLength];
 
                // The sentinel rejects an unavailable take.
                let take = -1000000000;
 
                // A fitting piece reads the current row.
                if (pieceLength <= rodLength) {
                    // Current-row reuse allows equal pieces.
                    const remainingRevenue = (
                        dp[index][rodLength - pieceLength]
                    );
 
                    // One piece adds price to the remainder.
                    take = price[index] + remainingRevenue;
                }
 
                // The larger choice completes the state.
                dp[index][rodLength] = Math.max(
                    notTake,
                    take
                );
            }
        }
 
        // The final cell represents every allowed choice.
        return dp[n - 1][n];
    }