换零钱

import java.util.Scanner;

/**
 * Created by Olive on 2017/8/6.
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            long countWay = changeWay(n);
            System.out.println(countWay);
        }
    }

    // 硬币组合也是一种背包问题
    public static long changeWay(int n){
        if(n <= 0)
            return 1;
        int[] money = {1, 5, 10, 25, 50};
        // dp[i]表示，i分钱可以有多少种表示方式
        long[] dp = new long[n + 1];
        dp[0] = 1;
        // 然后遍历所有的零钱情况
        for(int i = 0; i < 5; i++){
            for(int j = money[i]; j <= n; j++){
                dp[j] = dp[j] + dp[j - money[i]];
            }
        }
        return dp[n];
    }
}

经典的动态规划问题。给定零钱change = {1, 5, 10, 25, 50}，求target的兑换方法数。
其实这类问题非常经典且常用，例如自动贩卖机的自动找零程序，当然为了不找给顾客一
堆钢镚儿招致他的不满，需要零钱最少的方案数。此处单求找零钱的总方案数：
定义dp[i][j]的含义为：使用change[0] ~ change[i]兑换目标j的方法数，依次按行更新
完dp数组之后，最右下角的那个数就是使用给定的所有零钱兑换target的方案总数啦^-^!
按照动态规划一般的“三步走”策略(是我自己总结的三步走...)：
 
第一步：计算dp数组的第一行，第一行dp[0][ j ]的含义就是仅仅使用change[0]兑换j的
方案总数，这个就简单了， j能被change[0]整除，就代表有一种方案，反之就是没有方案。
 
第二步：计算dp数组的第一列，第一列dp[i][0]的含义就是，使用change[0 ~ i]兑换0元的
方法数，这个就更简单了，兑换0元那就是不换呗，方案数自然就是1。
 
第三步：也是最复杂的一步，需要定制dp的更新策略了，对于这个问题，dp[i][j]如何更新
呢?根据dp[i][j]所表示的含义,即兑换j的总方案数,我们有如下等式成立(其实就是组合问题)：
dp[i][j] (使用change[0 ~ i]兑换j)
= dp[i-1][j] (使用change[0 ~ i-1]兑换j，其实也就是使用0个change[i])
+ dp[i-1][j-change[i]]
        (使用change[0~i-1]兑换j-changes[i]，其实也就是使用1个change[i])
+ dp[i-1][j-2*change[i]]
        (使用change[0~i-1]兑换j-2*changes[i]，其实也就是使用2个change[i])
+...
+ dp[i-1][j-k*change[i]]
        (使用change[0~i-1]兑换j-k*changes[i]，其实也就是使用k个change[i])
当然这里k有个约束：0 < k 且 k*changes[i] <= j，对吧，不能比目标j还大吧。
 
我们把所有的方案累加起来就是兑换j的总方案数dp[i][j]，按照这个思路写的代码如下 
long long solution(vector<int> changes, int target){
    int n = changes.size();
    vector<vector<long long>> dp(n, vector<long long>(target + 1));
    for (int i = 0; i <= target; i++){
        if (i % changes[0] == 0)
            dp[0][i] = 1;
    }
    for (int i = 0; i < n; i++){
        dp[i][0] = 1;
    }
    for (int i = 1; i < n; i++){
        for (int j = 1; j <= target; j++){
            int num = 0;
            for (int k = 0; k*changes[i] <= j; k++)
                num += dp[i - 1][j - k * changes[i]];
            dp[i][j] = num;
        }
    }
    return dp[n - 1][target];
}
 
思路没有问题，但是时间复杂度有点高喂，仔细分析一下上述思路中dp[i][j]的构成，
分为k + 1个分式，我们把第一个式子看成一组，后面k个式子看成一组，那么第一组
式子表示的含义就是不使用change[i]的时候构成 j 的方案数；第二组式子的含义就是
使用了change[0 ~ i-1] + change[i]的时候构成 j 的方案数,并且这k个式子对使用1~k
个change[i]的情况进行了枚举！！那不就是使用了change[0 ~ i]吗?没错，那构成的钱
数是多少呢？是dp[i - 1][j - change[i]]，...，dp[i - 1][j - k * change[i]]，到
底是哪个呢?按最多的那个钱数算，没错的！所以第二组式子所表示的含义就是使用了
change[0 ~ i]构成dp[i - 1][j - change[i]]的总方案数！！！所以就有dp的更新公式
为：dp[i][j] = dp[i - 1][j] + dp[i][j - change[i]]，按照这个思路给出的求解方案
是： 
long long solution(vector<int> changes, int target){
    int n = changes.size();
    vector<vector<long long>> dp(n, vector<long long>(target + 1));
    for (int i = 0; i <= target; i++){
        if (i % changes[0] == 0)
            dp[0][i] = 1;
    }
    for (int i = 0; i < n; i++){
        dp[i][0] = 1;
    }
    for (int i = 1; i < n; i++){
        for (int j = 1; j <= target; j++){
            if (j < changes[i])
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = dp[i - 1][j] + dp[i][j - changes[i]];
        }
    }   
    return dp[n - 1][target];
}

//动态规划，思路在讨论区大同小异，在此仅记录一下自己的代码，仅参考！
#include<iostream>
#include<vector>
 
#define N 5
using namespace std;
int main(void)
{
    int m[N + 1] = { 0,1,5,10,25,50 };
    int money;
    while (cin >> money)
    {
        long long **dp = new long long *[N + 1];
        for (int i = 0; i <= N; i++)
            dp[i] = new long long[money + 1];
        //边界条件
        dp[0][0] = 1;
        for (int i = 1; i <= N; i++)
            dp[i][0] = 1;//第一列全部为1
        for (int i = 1; i <= money; i++)
            dp[0][i] = 0;//第一行全部为0
 
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= money; j++)
            {
                if (j >= m[i])
                    dp[i][j] = dp[i - 1][j] + dp[i][j - m[i]];
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        cout << dp[N][money] << endl;
        for (int i = 0; i < N + 1; i++)
            delete dp[i];
        delete[] dp;
    }
         
    return 0;
}

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <exception>
#include <iomanip>
#include <memory>
#include <sstream>

using namespace std;

int main(int argc, char** argv)
{
	//freopen("in.txt", "r", stdin);
	vector<int> input;
	int n, maxVal = 0;
	while (cin >> n)
	{
		input.emplace_back(n);
		maxVal = max(maxVal, n);
	}

	vector<long long> dp(maxVal + 1, 0), coins{ 1, 5, 10, 25, 50 };
	dp[0] = 1;
	for (auto& coin:coins)
		for (int j = coin; j <= maxVal; ++j)
			dp[j] += dp[j - coin];

	for (auto& i : input) cout << dp[i] << endl;

	return 0;
}

#include <iostream>
#include <vector>
using namespace std;
long countWays(vector<int> changes, int n, int x) {
	vector<long> vec(x+1,0);
    for(int i=0;i<n;i++){
    	if(changes[i]<=x){
        	vec[changes[i]]++;
        	for(int j=1;j+changes[i]<=x;j++)
            	vec[j+changes[i]]+=vec[j];
        }
    }
    return vec[x];
}
int main(){
    int N;
    int p[]={1,5,10,25,50};
    vector<int> vec(p,p+5);
    while(cin>>N){
        cout<<countWays(vec,5,N)<<endl;
    }
    return 0;
}

// write your code here
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()) {
            int m=sc.nextInt();
            int[] v= {1,5,10,25,50};
            long[] dp=new long[m+1];
            dp[0]=1;
            for(int i=0;i<v.length;i++) {
                for(int j=1;j<=m;j++) {
                    if(j>=v[i]) {
                        dp[j]+=dp[j-v[i]];
                    }
                }
            }
            System.out.println(dp[m]);
        }
    }
}

	

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] money = {1, 5, 10, 25, 50};
		while (sc.hasNext()) {
			int n = sc.nextInt();
			long[] dp = new long[n + 1];
			dp[0] = 1;
			for (int i = 0; i < money.length; i ++ ) {
				for (int j = money[i]; j < dp.length; j ++ ) {
					dp[j] += dp[j - money[i]];
				}
			}
			System.out.println(dp[n]);
		}
	}
}

import java.util.*;
public class Main{
    private static int[] change = {1,5,10,25,50};
    public static void main(String[] args){       
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
			int money = in.nextInt();
            System.out.print(Exchange(money,change.length));
        }
    }
    
    private static int Exchange(int money,int n){
        if(money==1){
            return 1;
        }else if(money<0||n==0){
            return 0;
        }else{
            return Exchange(money,n-1) + Exchange(money-change[n-1],n);
        }
    }
}

可使用母函数法
#include<iostream>
#include<string.h>
#define MAXNUM 10001      //最高次数
unsigned long a[MAXNUM];  
unsigned long b[MAXNUM];
unsigned long c[MAXNUM];  //保存结果

void Poly()       //多项式相乘
{
	int i;
	int j;
	memset(c, 0, sizeof(c));   //将数组c全部初始化为0；
	for (i = 0; i < MAXNUM; i++)
	{
		for (j = 0; j < MAXNUM - i; j++)    //j < MAXNUM - i,确保i+j不越界
		{
			c[i + j] += a[i] * b[j];    
		}
	}
}

int main()
{
	for (int i = 0; i < MAXNUM; i++)
	{
		a[i] = 1;
	}
	int num[5] = { 1,5,10,25,50 };
	for (int i = 1; i < 5; i++)
	{
        memset(b,0,sizeof(b));
		for (int j = 0; j < MAXNUM; j += num[i])
		{
			b[j] = 1;
		}
		Poly();
		memcpy(a, c, sizeof(c));
	}
	int input;
	while (std::cin >> input)
		std::cout << a[input] << std::endl;
	//system("pause");
	return 0;
}

#include <iostream>

const int N = 10000;

long dp[N + 1] = {0};
int MON[5] = {1,5,10,25,50};

int main()
{
  dp[0] = 1;
  for (int i = 0; i < 5; ++i) {
    for (int j = MON[i]; j < N + 1; ++j ) {
            dp[j] += dp[j - MON[i]];
        }
    }

  int n;
  while (std::cin>>n) {
      std::cout << dp[n] << "\n";
  }
}

for (int v = N; v >= MON[i]; --v)

// write your code here cpp
#include <iostream>
using namespace std;
//typedef int MM[5];
int main()
{
 int N;
 int MON[5]{1,5,10,25,50};
 while(cin>>N)
 {
 unsigned long long **dp = new unsigned long long *[2];
 dp[0] = new unsigned long long [N+1];
 dp[1] = new unsigned long long [N+1];
 for(int i=0;i<N+1;i++)
 {
 dp[0][i] = (i>=MON[0])?MON[0]:0;
 }
 dp[0][0] = 1;
 dp[1][0] = 1;
 for(int i = 1;i<5;i++)
 {
 for(int j=1;j<N+1;j++)
 {
 if( j >= MON[i])
 {
 dp[1][j] = dp[0][j] + dp[1][j-MON[i]];
 }
 else
 {
 dp[1][j] = dp[0][j];
 }
 }
 for(int kk=0;kk<N+1;kk++)
 {
 dp[0][kk] = dp[1][kk];
 }
 }
 cout<<dp[1][N]<<endl;
 delete []dp[0];
 delete []dp[1];
 delete []dp;
 }



 return 0;
}

/** 答案错误:您提交的程序没有通过所有的测试用例

172016955 严重怀疑测试用例答案有错误，用了各种方法，答案都是一样的
ps：如果哪位大神通过了，请告知：9001的结果到底是什么 >_< 

不管怎样，用的动态规划的思想，这道题是一个整数划分的变形，一般整数划分的加数都是连续的数，从1~n都可以是划分后的加数，这里限定了划分后的加数只能是1,5,10,25,50这5个数。
A.没有限定加数情况的状态转移方程：有两种情况：
    1.n>=m: dp[n][m] = dp[n][m-1] + dp[n-m][m],
    2.n<m: dp[n][m] = dp[n][n],
    其中dp[n][m]表示整数n在加数不大于m的情况下的划分个数。
B.在限定加数的情况下：（以此题为例，加数按顺序放入数组v中）
    初始：dp[k][v[0]] = 1; 0<=k<=maxn;
    1.n>=v[i]: dp[n][v[i]] = dp[n][v[i-1]] + dp[n-v[i]][v[i]]; 1<=i<=4
    2.n<v[i]: dp[n][v[i]] = dp[n][v[i-1]]
**/
import java.util.Scanner;

public class Main {

	public static final int maxn = 10000;
	
	public static final int[] v = {1,5,10,25,50};
	
	public static int[][] f = new int[maxn+1][51];
	
	public static void dp(){
		for(int i=0;i<=maxn;i++){
			f[i][v[0]] = 1;
		}
		for(int i=0;i<=maxn;i++){
			for(int j=1;j<5;j++){
				if(v[j]<=i)
					f[i][v[j]] = f[i][v[j-1]] + f[i-v[j]][v[j]];
				else
					f[i][v[j]] = f[i][v[j-1]];
			}
		}
	}
	
	public static void main(String[] args) {
		dp();
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int n = sc.nextInt();
			System.out.println(f[n][v[4]]);
		}
	}
}