dp-找零钱方程.txt

#include <vector>
#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;

vector<int> coin = { 1,4,16,64 };

int changeCoin(vector<int>& coin, int amount) {
	int m = amount + 1;
	vector<int>dp(amount + 1, m);
	dp[0] = 0;
	for (int i = 1; i <= amount; i++) {
		for (int j = 0; j < coin.size(); j++) {
			if (i - coin[j] >= 0) {
				dp[i] = min(dp[i], dp[i - coin[j]] + 1);


			}


		}
	}
	return dp[amount] > amount ? -1 : dp[amount];
}

int main() {
	int n;
	while (cin >> n) {
		int re = changeCoin(coin, 1024 - n);
		cout << re;

	}


	return 0;
}