Untitled diff
5 removals
47 lines
13 additions
55 lines
DP_TABLE_ENTRY CC(int amt,unsigned int denom_count)
DP_TABLE_ENTRY DP_CC(int amt,unsigned int denom_count)
{
{
unsigned int n = denom_count;
unsigned int n = denom_count;
DP_TABLE_ENTRY ret = {0};
DP_TABLE_ENTRY ret = {0};
/* Calls with a negative amount are not stored.
/* Calls with a negative amount are not stored.
* Just need to return count= 0.
* Just need to return count= 0.
*/
*/
if(amt <0)
if(amt <0)
{
{
ret.runtime = 1; /* constant runtime */
ret.runtime = 1; /* constant runtime */
ret.count = 0;
ret.count = 0;
}
}
/* Precomputed value, just need to update number of references
* to this value.
*/
else if(DP_TABLE[amt][n].references != 0)
{
DP_TABLE[amt][n].references++;
DP_TABLE[amt][n].runtime = 1; /* constant runtime. */
return DP_TABLE[amt][n];
}
else if(n==0)
else if(n==0)
{
{
DP_TABLE[amt][n].count = 0;
DP_TABLE[amt][n].count = 0;
DP_TABLE[amt][n].references++;
DP_TABLE[amt][n].references++;
DP_TABLE[amt][n].runtime = 1; /* constant runtime. */
DP_TABLE[amt][n].runtime = 1; /* constant runtime. */
ret = DP_TABLE[amt][n];
ret = DP_TABLE[amt][n];
}
}
else if(amt == 0 )
else if(amt == 0 )
{
{
DP_TABLE[amt][n].count = 1;
DP_TABLE[amt][n].count = 1;
DP_TABLE[amt][n].references++;
DP_TABLE[amt][n].references++;
DP_TABLE[amt][n].runtime = 1; /* constant runtime. */
DP_TABLE[amt][n].runtime = 1; /* constant runtime. */
ret = DP_TABLE[amt][n];
ret = DP_TABLE[amt][n];
}
}
else
else
{
{
DP_TABLE_ENTRY left,right = {0};
DP_TABLE_ENTRY left,right = {0};
int new_amt = amt- maxDenom(n);
int new_amt = amt- maxDenom(n);
int new_n = n-1;
int new_n = n-1;
left = CC(amt,new_n);
left = DP_CC(amt,new_n);
right = CC(new_amt,n);
right = DP_CC(new_amt,n);
DP_TABLE[amt][n].count = left.count + right.count;
DP_TABLE[amt][n].count = left.count + right.count;
DP_TABLE[amt][n].references++;
DP_TABLE[amt][n].references++;
DP_TABLE[amt][n].runtime=left.runtime + right.runtime + 1; /* Runtime of sub-problems + time to conbine their results. */
DP_TABLE[amt][n].runtime=left.runtime + right.runtime + 1; /* Runtime of sub-problems + time to conbine their results. */
ret = DP_TABLE[amt][n];
ret = DP_TABLE[amt][n];
}
}
return ret;
return ret;
}
}