usaco_money

Money Systems
The cows have not only created their own government but they have chosen to create their own money system. In their own rebellious way, they are curious about values of coinage. Traditionally, coins come in values like 1, 5, 10, 20 or 25, 50, and 100 units, sometimes with a 2 unit coin thrown in for good measure.
The cows want to know how many different ways it is possible to dispense a certain amount of money using various coin systems. For instance, using a system of {1, 2, 5, 10, ...} it is possible to create 18 units several different ways, including: 18x1, 9x2, 8x2+2x1, 3x5+2+1, and many others.
Write a program to compute how many ways to construct a given amount of money using supplied coinage. It is guaranteed that the total will fit into both a signed long long (C/C++) and Int64 (Free Pascal).
PROGRAM NAME: money
INPUT FORMAT
The number of coins in the system is V (1 <= V <= 25).
The amount money to construct is N (1 <= N <= 10,000).
Line 1:
Two integers, V and N
Lines 2..:
V integers that represent the available coins (no particular number of integers per line)
SAMPLE INPUT (file money.in)

3 10
1 2 5

OUTPUT FORMAT
A single line containing the total number of ways to construct N money units using V coins.
SAMPLE OUTPUT (file money.out)

10
     dp ，  ，    ，        N  。。。   

#include <fstream>
using namespace std;

ifstream fin("money.in");
ofstream fout("money.out");

#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif

long long dp[10001];
int coins[25];

void solve()
{
    dp[0] = 1;

    int v,n;

    in>>v>>n;

    for(int i=0;i<v;++i)
        in>>coins[i];

    for(int i=0;i<v;++i){
        for(int j=0;j+coins[i]<=n;++j){
            dp[j+coins[i]]+=dp[j];
        }
    }

    out<<dp[n]<<endl;
}

int main(int argc,char *argv[])
{
    solve(); 
    return 0;
}

 

             ，    ：

      ，      ，          noip              ，         ，        ，                    。 

                     ，         O(v*n*n)、     O(V*n)     ，           。 

             ，         O(v*n)、     O(v*n)   ，                                 。 

             O(v*n)、     O(n)   ,                      ，             。 

 ：ways[i][j]    i    ，     j      

  1： 

       ，             。  ，     “  ”，                。 

       ：     ，  v ，                ，                 ，                 ，                           ，                    n 。 

      ：     i      m   ，                ，         n ，        “  i        m   ” 

      ，    0      ，          ，      m              i-1      j-m×units[i]       ，  units[i]  i         。 

               ，       ： ways[i][j] = Sum(ways[i - 1][j - m * units[i]]) {m = 0、1、2、……、k}，k          。 

   ，       ways     ，  v * n,          n，            O(v*n*n) 

        code1 

/**//*
ID: sdjllyh1
PROG: money
LANG: JAVA
complete date: 2008/12/18
complexity: O(v * n * n)
author: LiuYongHui From GuiZhou University Of China
more article: www.cnblogs.com/sdjls
*/

import java.io.*;
import java.util.*;

public class money
{
    private static int v, n;
    private static long[][] ways;//ways[i][j]    i    ，     j     
    private static int[] units;//     
    private static long answer;

    public static void main(String[] args) throws IOException
    {
        init();
        run();
        output();
        System.exit(0);
    }

    private static void run()
    {
        //    ，     j  ，  j          ，  ways[0][j]=1
        for (int j = 1; j <= n; j++)
        {
            if (j % units[0] == 0)
            {
                ways[0][j] = 1;
            }
            else
            {
                ways[0][j] = 0;
            }
        }
        //    ，     0  ，    1
        for (int i = 0; i < v; i++)
        {
            ways[i][0] = 1;
        }
        // ways[i][j]
        for (int i = 1; i < v; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                int multiple = 0;// i        
                //   i           j 
                while (multiple * units[i] <= j)
                {
                    ways[i][j] += ways[i - 1][j - multiple * units[i]];
                    multiple++;
                }
            }
        }

        answer = ways[v - 1][n];//   i  0   v-1
    }
    
    private static void init() throws IOException
    {
        BufferedReader f = new BufferedReader(new FileReader("money.in"));
        StringTokenizer st = new StringTokenizer(f.readLine());
        v = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        units = new int[v];
        int index = 0;
        String readLine = f.readLine();
        while (readLine != null)
        {
            st = new StringTokenizer(readLine);    
            while (st.hasMoreTokens())
            {
                units[index] = Integer.parseInt(st.nextToken());
                index++;
            }
            readLine = f.readLine();
        }
        f.close();

        ways = new long[v][n + 1];
    }

    private static void output() throws IOException
    {
        PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("money.out")));
        out.println(answer);
        out.close();
    }
} 

  2： 

                              ，  ： 

          ，              “  i              ？”，    “  i                ？（    ，         ）” 

         “    （    O(n)）” “    （    O(1)）”，        ，          。 

  1          “  i-1         j-m*units[i]    ”，   2      “         ，  i         j - units[i]    ” “      ，  i         j    ”，  “     ”        。 

          ：ways[i][j] = ways[i][j-units[i]] + ways[i-1][j]，ways[i][j-units[i]]        ，ways[i-1][j]              。 （  ：   i       m   ， m>0 ，        ways[i][j-units[i]]   ，                m=0   。）

                    ，         O(v*n) 

          code2 
    private static void run()
    {
        
        for (int j = 1; j <= n; j++)
        {
            if (j % units[0] == 0)
            {
                ways[0][j] = 1;
            }
            else
            {
                ways[0][j] = 0;
            }
        }
        
        for (int i = 0; i < v; i++)
        {
            ways[i][0] = 1;
        }
        
        for (int i = 1; i < v; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                //   i      ，              i      
                if (j - units[i] >= 0)
                {
                    ways[i][j] = ways[i - 1][j] + ways[i][j - units[i]];
                }
                else
                {
                    ways[i][j] = ways[i - 1][j];
                }
            }
        }

        answer = ways[v - 1][n];
    }

 

  3： 

     2      ：ways[i][j] = ways[i][j-units[i]] + ways[i-1][j] 

    ways[i][*]     ways[i-1][*]，     ways[i-2][*],ways[i-3][*]  。 

    ，                  ways  ，   v ，        ： ways_2[j] = ways_2[j-units[i]] + ways_1[j]。 

   ways_2[j] ，ways_2[j]              ways_2[j]    （       ways_2[j-units[i]] ways_1[j]   ）， 

        ways_2[j]    ways_1[j]  ，      ： ways_2[j] = ways_2[j-units[i]] + ways_2[j]。 

  ，   ways_2[j] = ways_2[j-units[i]] + ways_2[j] ，     ways_2[j]  “ i     j     ”，      ways_2[j]  “ i-1     j     ”。 

           O(n) ways   。     O(v*n)    O(n)。 

          code3 
 private static void run()
    {
        
        for (int j = 0; j <= n; j++)
        {
            if (j % units[0] == 0)
            {
                ways[j] = 1;
            }
            else
            {
                ways[j] = 0;
            }
        }
        
        for (int i = 1; i < v; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                //   i      ，              i      
                if (j - units[i] >= 0)
                {
                    ways[j] = ways[j] + ways[j - units[i]];
                }
                else
                {
                    ways[j] = ways[j];
                }
            }
        }

        answer = ways[n];
    }