The following combinations method is very inefficient. Same values are calculate
ID: 3606584 • Letter: T
Question
The following combinations method is very inefficient. Same values are calculated over and over. For example, combinations (4, 3) is calculated in two different places. One could apply dynamic programming here, using extra memory, solutions to sub-problems that are needed repeatedly should be saved in a data structure instead of being recalculated. Using dynamic programming, make the combinations method efficient. Show your changes below. Also, comment on the improvement in time complexity by doing so. And please use Java.
static int combinations (int group, int members)
{
if (members == 1)
return group; // Base case 1
else if (members == group)
return 1; // Base case 2
else
return (combinations(group - 1, members - 1) + combinations(group - 1, members));
}
Explanation / Answer
Please find my implementation.
static int combinations(int group, int members, int[][] array) {
// if we have already calculated then return value
if(array[group][members] != Integer.MIN_VALUE)
return array[group][members];
if(members == 1) {
array[group][members] = group;
return group;
}
else if(members == group){
array[group][members] = 1;
return 1;
}
int x = combinations(group-1, members-1, array);
int y = combinations(group-1, members, array);
array[group][members] = x+y;
return array[group][members] ;
}
static int combinations(int group, int members) {
int[][] array = new int[group+1][members+1];
for(int i=0; i<=group; i++) {
for(int j=0; j<=members; j++)
array[i][j] = Integer.MIN_VALUE; // initializing with sentinel value
}
return combinations(group, members, array);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.