nyoj 995硬币找零（dp）遞推

遞推：（自底向上，從小到大）

　　　　由遞推關系式：dp(T) = min(dp(T - vi)) + 1, 其中T-vi < T是恒成立，是以可以保證從小大到遞推，在計算dpT)時，dp(T-vi)的值已經得到。

　　　　由于dp(T)的值需要有dp(T-vi)的值得到，是以遞推方法需要數組記錄dp(1)……dp(T)的值，這樣當dp(T) = 0時，可以從dp(T)向下周遊數組，找到第一個dp(t) !=0 即可。

　　　　在遞推過程中，還可以通過數組記錄，得到每個T是由哪種方式組合得到，使得需要硬币數最少

AC代碼如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn1=50+5;
const int maxn2=1e5+10;
int v[maxn1];
int dp[maxn2];
int n;
int main(){
	int T;
	while(scanf("%d%d",&n,&T)==2 && (n||T)){
		for(int i=1;i<=n;i++)scanf("%d",&v[i]);
		dp[0]=0;
		for(int i=1;i<=T;i++)dp[i]=maxn2;
		for(int i=1;i<=T;i++){
			for(int j=1;j<=n;j++){
				if(i>=v[j])dp[i]=min(dp[i],dp[i-v[j]]+1);
			}
		} 
	    for(int i=T;i>=0;i--)
	    	if(dp[i]!=maxn2){
	    		printf("%d\n",dp[i]);
	    		break;
			}
		}
	return 0;
}