【C++题解】100103.取钱
题目描述
六一儿童节到了，小涵想买个玩具送给她姐姐，但是，她的钱全部都放在银行，她想去银行取N元。
但是银行只有三种面值的货币:
- 第一种是1元面值。
- 第二种是6的次方的面值如6、62、63......
- 第三种是9的次方的面值如9、92、93......
提取N元至少总共可以提取多少张纸币。
输入格式
一个真整数N，代表涵涵要提取的数额。
输出格式
输出一个整数，代表涵涵提取N元，至少可以提取多少张纸币。
输入/输出例子1
输入：
127
输出：
4
输入/输出例子2
输入：
3
输出：
3
输入/输出例子3
输入：
44852
输出：
16
数据范围
1 ≤ N ≤ 100000，N为整数
样例解释：
样例1解释：
1元+9元+36(6^2) 元+81(9^2)=127，总共使用了4张纸币就可以组成了127元，也就是涵涵至少可以获得4张纸币。
样例2解释：
三张1元可以等到涵涵所需要的3元，也就是涵涵至少可以获得3张纸币。
参考答案
#include<bits/stdc++.h> #include<vector> using namespace std; int main() { int N; cin >> N; vector<int> coins = {1}; for (int i = 6; i <= N; i *= 6) { coins.push_back(i); } for (int i = 9; i <= N; i *= 9) { coins.push_back(i); } vector<int> dp(N + 1, INT_MAX); dp[0] = 0; for (int i = 1; i <= N; ++i) { for (int coin : coins) { if (i >= coin && dp[i - coin] != INT_MAX) { dp[i] = min(dp[i], dp[i - coin] + 1); } } } cout << dp[N] << endl; return 0; }题目链接：
https://v1.51goc.com/question/viewProgram/100103
（进去后要登录）