Getting Segmentation Fault

Question

Given an integer N denoting the Length of a line segment. you need to cut the line segment in such a way that the cut length of a line segment each time is integer either x , y or z. and after performing all cutting operation the total number of cutted segments must be maximum.

#include <iostream>
#include<vector>
#include<math.h>
#include<climits>
#include<algorithm>
using namespace std;

int count(int*dp,int x,int y,int z,int N)
{
    if(N==0)
    {
        return 1;
    }
    if(N<0)
    {
        return 0;
    }
    if(dp[N]!=INT_MAX)
    {
        return dp[N];
    }
        dp[N]=max(count(dp,x,y,z,x)+count(dp,x,y,z,N-x)
                ,max(count(dp,x,y,z,y)+count(dp,x,y,z,N-y),
                count(dp,x,y,z,z)+count(dp,x,y,z,N-z)));
    return dp[N];
}
int main() 
{
    //code
    int t;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        int n;
        cin>>n;
        int x,y,z;
        cin>>x;
        cin>>y;
        cin>>z;
        //cout<<x<<y<<z<<n;
        int*dp=(int*)malloc(sizeof(int)*n+1);
      // int dp[n+1];
        dp[0]=1;
        for(int i=1;i<=n;i++)
        {
            dp[i]=INT_MAX;
        }
        cout<<x<<y<<z<<n;
        cout<<count(dp,x,y,z,n)<<endl;
    }
    return 0;
}

[Debug your program](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). Don't dump it on us. — StoryTeller - Unslander Monica, Sep 26 '17 at 07:09
First of all don't use `malloc` in C++, use `new[]` instead. Then learn to not use dynamic allocation at all in situations like this, use [`std::vector`](http://en.cppreference.com/w/cpp/container/vector) instead. Lastly, while you might allocate enough space to use 1-based array (or vector) indexes, please avoid that as well as it might confuse just about everyone reading your code. — Some programmer dude, Sep 26 '17 at 07:09
As for your problem, have you checked that your recursion isn't to deep? Do you get a crash for *all* input? Or only for some input? — Some programmer dude, Sep 26 '17 at 07:11
`sizeof(int)*n+1` should be `sizeof(int)*(n+1)` if you want to allocate space for `n+1` integers. Your code is allocating enough space for 1 integer plus 1 extra byte. — Barmar, Sep 26 '17 at 07:11
Be [scared](https://stackoverflow.com/a/25636788/841108) of UB; SO is *not* a fix-my-code service. — Basile Starynkevitch, Sep 26 '17 at 07:11
And if you'd used `new int[n+1]` you wouldn't have had that problem. — Barmar, Sep 26 '17 at 07:13

Christophe · Answer 1 · 2017-09-26T15:14:23.217

1

Important remark about memor allocation in C++

C++ is not C. malloc() should really be avoided in C++, because it doesn't take care of the object lifecycle and hence requires a placement new when it is used for types that are not trivially copiable.

C++ memory allocation should use new (or make_unique or make_shared in combination with smart pointers), when it is needed.

But the best is to avoid using memory allocation, and rely instead on the safer and more powerful containers, such as for example vectors.

Your issue

This being said, int is trivially copyable, and all you need to make it work is to correct the size formula to sizeof(int)*(n+1). It's because your loop goes until n included, so that your array has to hold n+1 elements.

edited Sep 26 '17 at 15:14

answered Sep 26 '17 at 07:14

Christophe

68,716
7
72
138

@user0042 ok, i wanted to remain simple to facilitate the OP transition from C to C++. But you are right and I've edited the answer accordingly – Christophe Sep 26 '17 at 15:16
I didn't DV your answer BTW. – user0042 Sep 26 '17 at 15:41
@user0042 no problem at all ! Even if you would, a DV and some constructive critical comments are always helpful to improve quality of contributions. Thanks. – Christophe Sep 26 '17 at 15:53

Getting Segmentation Fault

1 Answers1