-1

I don't understand where I did wrong because whenever I ran the code the output is 35 but when I ran it on non-Top Down it's 22 ( which is the correct output from what I can see in Geeks4Geeks https://www.geeksforgeeks.org/cutting-a-rod-dp-13/)

Where did I go wrong?

#include <iostream>
#include <cstring>
#include <limits.h>
using namespace std;

int arr[1000];
int Cut_Rod(int p[], int n);

int main() {
    int p[] = { 1, 5, 8, 9, 10, 17, 17, 20 };
    int n = sizeof(p)/sizeof(p[0]) - 1;
    memset(arr, -1, sizeof(arr)); // set all values inside arr as -1
    int maxValue = Cut_Rod(p, n);
    cout << "Max profit: " << maxValue << endl;

    return 0;
}

int Cut_Rod(int p[], int n) {
    int q;
    if (arr[n] >= 0)
        return arr[n];
    if (n == 0)
        q = 0;
    else {
        q = INT_MIN;
        for (int i = 1; i <= n; i++) {
            q = max(q, p[i] + Cut_Rod(p, n - i));
        }
    }
    arr[n] = q;
    return q;
}
Powzer
  • 19
  • 5
  • While `memset(arr, -1, sizeof(arr))` might work, it's not really the right C++ way to set all values in a container to a specific value. For that use [`std::fill`](https://en.cppreference.com/w/cpp/algorithm/fill). As in `std::fill(std::begin(arr), std::end(arr), -1)`. Also your use of arrays and global variables are discouraged. I would recommend you use `std::vector` that can be dynamically added to, if you don't need that many elements, or if you need more. – Some programmer dude Apr 04 '23 at 10:45
  • 3
    And a small note about the *Geek for geeks* site: It have a really bad reputation around here and with experienced programmers. Like many similar sites it tends to teach bad habits, bad code and sometimes even invalid code. If you can then please invest in [some good C++ books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) to learn C++ "properly". – Some programmer dude Apr 04 '23 at 10:47
  • @Someprogrammerdude Thanks! The reason why I use it in the first place is because I saw teacher using it as reference in the class alongside w3school so I thought it was trustworthy. – Powzer Apr 04 '23 at 10:48
  • 1
    @Powzer that puts your teacher in a very bad light regarding their seriosity (same for w3school). – πάντα ῥεῖ Apr 04 '23 at 10:52
  • 2
    w3schools is even worse than geeks4geeks – john Apr 04 '23 at 10:55
  • 1
    whilst `memset(arr, -1, sizeof(arr))` might work, it is mostly by chance, try running `memset(arr, -2, sizeof(arr))` and you'll see why `memset` is a bad idea for anything other than setting bytes or setting to `0` – Alan Birtles Apr 04 '23 at 11:31

1 Answers1

2

You have an off by one error. Your prices array p is indexed by length with the minimum length being 1, but the first price in your array is at index zero. Your code never accesses p[0].

The simplest fix is to add a dummy value to the start of your prices array.

int p[] = { 0, 1, 5, 8, 9, 10, 17, 17, 20 };

With that change the code prints 22 as expected.

john
  • 85,011
  • 4
  • 57
  • 81
  • Is it possible to do it without adding the dummy value? – Powzer Apr 04 '23 at 11:13
  • @Powzer Yes of course. The alternative is to subtract one when you access the `p` array. So `p[i - 1] + Cut_Rod(p, n - i)` should do it. – john Apr 04 '23 at 11:46