dp-rod_cutting_problem

mail@pastecode.io avatar
unknown
plain_text
a year ago
703 B
9
Indexable
Never
class Solution{
  public:
  
  
    int cutRod(int price[], int n) {
        int length = n ;
        //  int size  = sizeof(price) / sizeof(int);
        int size=n;
        int l[size]={0};
        for(int i=0;i<size;i++)l[i]=i+1;
        int t[size+1][length+1];
        
        for (int i = 0; i <=size; i++)
		for (int j = 0; j <= length; j++)
			if (j == 0 || i == 0)
				t[i][j] = 0;
				
        // memset(t,0,sizeof(t));
        
        for(int i=1;i<size+1;i++){
            for(int j=1;j<length+1;j++){
                if(l[i-1]<=j) t[i][j]= max(price[i-1]+t[i][j-l[i-1]], t[i-1][j]);
                else t[i][j]= t[i-1][j];
            }
        }
        return t[size][length];
    }
};