Rod Cutting Problem in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to return the maximum price for a rod of length n.

DSA C

int cutRod(int price[], int n) {
    if (n <= 0) return 0;
    int max_val = [1];
    for (int i = 1; i <= n; i++) {
        int val = price[i - 1] + cutRod(price, n - i);
        if (val > max_val) max_val = val;
    }
    return max_val;
}

Drag options to blanks, or click blank then click option'

A1

B-1

C0

DINT_MIN

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing max_val to 0 causes incorrect results when all prices are negative.

Using 1 or -1 does not correctly represent the smallest integer.

We initialize max_val with INT_MIN to ensure any computed value will be larger, allowing correct maximum calculation.

2fill in blank

medium

Complete the code to implement the bottom-up dynamic programming approach for rod cutting.

DSA C

int cutRodDP(int price[], int n) {
    int val[n+1];
    val[0] = 0;
    for (int i = 1; i <= n; i++) {
        int max_val = [1];
        for (int j = 1; j <= i; j++) {
            max_val = max(max_val, price[j-1] + val[i-j]);
        }
        val[i] = max_val;
    }
    return val[n];
}

Drag options to blanks, or click blank then click option'

A0

B-1

CINT_MIN

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using INT_MIN causes unnecessary complexity in bottom-up approach.

Starting max_val at -1 or 1 can cause incorrect maximum calculations.

In bottom-up DP, max_val starts at 0 because prices are non-negative and we want to find the maximum.

3fill in blank

hard

Fix the error in the recursive rod cutting function to avoid infinite recursion.

DSA C

int cutRod(int price[], int n) {
    if (n == 0) return 0;
    int max_val = INT_MIN;
    for (int i = 1; i <= n; i++) {
        int val = price[i - 1] + cutRod(price, [1]);
        if (val > max_val) max_val = val;
    }
    return max_val;
}

Drag options to blanks, or click blank then click option'

An - i

Bn + i

Ci

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using n + i causes infinite recursion.

Using n or i directly does not reduce problem size correctly.

We reduce the rod length by i to avoid infinite recursion and correctly compute subproblems.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps rod lengths to their maximum prices for lengths greater than 0.

DSA C

int maxPrices[[1]];
for (int i = 1; i <= [2]; i++) {
    maxPrices[i-1] = cutRodDP(price, i);
}

Drag options to blanks, or click blank then click option'

An

Bn+1

Cn-1

Dn*2

Attempts:

3 left

💡 Hint

Common Mistakes

Using n causes out-of-bound errors for length n.

Using n-1 misses the last rod length.

We use n+1 to include length n in the loop and array size to store max prices for all lengths up to n.

5fill in blank

hard

Fill all three blanks to complete the memoized rod cutting function.

DSA C

int memoCutRod(int price[], int n, int memo[]) {
    if (n == 0) return 0;
    if (memo[[1]] >= 0) return memo[[2]];
    int max_val = INT_MIN;
    for (int i = 1; i <= n; i++) {
        int val = price[i - 1] + memoCutRod(price, n - i, memo);
        if (val > max_val) max_val = val;
    }
    memo[[3]] = max_val;
    return max_val;
}

Drag options to blanks, or click blank then click option'

An

Bn-1

C0

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using n causes out-of-bound errors.

Using 0 or 1 does not correspond to current rod length.

We use n-1 as index because array indices start at 0 for rod length n.