## 2013年9月28日 星期六

### UVA 147 - Dollars

Keyword: DP

Algorithm:

Let ans[ i ][ j ] stands for the number of ways to use j kinds of the smallest face value of bill to get i dollars.
The base case: ans[ 0 ][ n ] = 1(always one way to get 0 dollar), ans[ n ][ 0 ] = 0(no way to get n dollars from 0 kind of coins).
If i >= coin[ j ], then we can use that coin and don't use that. (ans[ i ][ j ] = ans[ i-coin[ j ] ][ j ] + ans[ i ][ j-1 ])
If i < coin[ j ], then we can't use that kind of coin for sure. (ans[ i ][ j ] = ans[ i ][ j-1 ])
The last column of each row(dollar) is the answer.

Code:
```#include<cstdio>
const int coin[] = { 0, 1, 2, 4, 10, 20, 40, 100, 200, 400, 1000, 2000 };

int main()
{
int dec, flo;
long long int ans[ 6001 ][ 12 ] = { 0 };
for( int i = 0; i <= 11; ++i )
ans[ 0 ][ i ] = 1;
for( int i = 1; i <= 6000; ++i )
for( int j = 1; j <= 11; ++j )
if( i >= coin[ j ] )
ans[ i ][ j ] = ans[ i-coin[ j ] ][ j ] + ans[ i ][ j-1 ];
else
ans[ i ][ j ] = ans[ i ][ j-1 ];

while( scanf( "%d.%d", &dec, &flo ) && dec+flo )
printf( "%3d.%02d%17lld\n", dec, flo, ans[ dec*20 + flo/5 ][ 11 ] );

return 0;
}```