Uva 674 ---- coin change

1. // coin change
2. #include <iostream>
3. using namespace std;
4. int main()
5. {
6. int iCoin[7490][5];
7. int iMoney[5] = { 1, 5, 10 , 25, 50 };
8. int iAmount, i ,j, iMax;
10. while ( cin >> iAmount )
11.     {
12.     iMax = -1; 
13.     for ( i=0 ; i<=iAmount ; i++ ) 
14.         iCoin[i][0] = 1;
15.     for ( j=0 ; j<5 ; j++ )
16.         iCoin[0][j] = 1;
17.     for ( i=1 ; i<=iAmount ; i++ )     
18.         for ( j=1 ; j<5 ; j++ )
19.             {
20.             if ( i-iMoney[j] >= 0 )
21.                 iCoin[i][j] = ( iCoin[i][j-1] + iCoin[i-iMoney[j]][j] );   
22.             else
23.                 iCoin[i][j] = iCoin[i][j-1];   
24.                
25.             }
26.     /*     
27.     for ( i=0 ; i<iAmount ; i++ )      
28.         {
29.         for ( j=0 ; j<5 ; j++ )
30.             cout << iCoin[i][j] << " ";
31.         cout <<endl;
32.         }
33.     */
34.     for ( j=0 ; j<5 ; j++)
35.         if ( iCoin [iAmount][j] > iMax )
36.             iMax = iCoin[iAmount][j];
37.     cout << iMax <<endl;       
38.     }
39.    
40.    
41.    
42. }

擷取自老師上課投影片