What is space complexity of the following dynamic programming implementation of the dice throw problem where f is the number of faces, n is the number of dice and s is the sum to be found?
#include<stdio.h>
int get_ways(int num_of_dice, int num_of_faces, int S)
{
int arr[num_of_dice + 1][S + 1];
int dice, face, sm;
for(dice = 0; dice <= num_of_dice; dice++)
for(sm = 0; sm <= S; sm++)
arr[dice][sm] = 0;
for(sm = 1; sm <= S; sm++)
arr[1][sm] = 1;
for(dice = 2; dice <= num_of_dice; dice++)
{
for(sm = 1; sm <= S; sm++)
{
for(face = 1; face <= num_of_faces && face < sm; face++)
arr[dice][sm] += arr[dice - 1][sm - face];
}
}
return arr[num_of_dice][S];
}
int main()
{
int num_of_dice = 3, num_of_faces = 4, sum = 6;
int ans = get_ways(num_of_dice, num_of_faces, sum);
printf("%d",ans);
return 0;
}
#include<stdio.h>
int get_ways(int num_of_dice, int num_of_faces, int S)
{
int arr[num_of_dice + 1][S + 1];
int dice, face, sm;
for(dice = 0; dice <= num_of_dice; dice++)
for(sm = 0; sm <= S; sm++)
arr[dice][sm] = 0;
for(sm = 1; sm <= S; sm++)
arr[1][sm] = 1;
for(dice = 2; dice <= num_of_dice; dice++)
{
for(sm = 1; sm <= S; sm++)
{
for(face = 1; face <= num_of_faces && face < sm; face++)
arr[dice][sm] += arr[dice - 1][sm - face];
}
}
return arr[num_of_dice][S];
}
int main()
{
int num_of_dice = 3, num_of_faces = 4, sum = 6;
int ans = get_ways(num_of_dice, num_of_faces, sum);
printf("%d",ans);
return 0;
}A. O(n*f)
B. O(f*s)
C. O(n*s)
D. O(n*f*s)
Answer: Option C

Join The Discussion