2023年11月25日发(作者：苹果8图片颜色)

⼩⽶2020校招笔试题及答案

这⾥⽤的是动态规划做的，递归⽅程是：dp[i] = dp[i - prices[j]] + 1;

package com.test;

import java.io.*;

import java.util.*;

import java.text.*;

import java.math.*;

import java.util.regex.*;

public class Test4 {

/*

* ^-^

请完成下⾯这个函数，实现题⽬要求的功能当然，你也可以不按照下⾯这个模板来作答，完全按照⾃⼰的想法来开始写代码

******************************/

static int solution(int[] prices, int budget) {

//

定义⼀个每个预算可买最少产品的数组

int[] dp = new int[budget + 1]; // 00

预算为可买件

for (int i = 1; i <= budget; i++) {

for (int j = 0; j < prices.length; j++) {

if (prices[j] <= i) {

dp[i] = dp[i - prices[j]] + 1;

}

}

System.out.println("预算为" + i + "需要的最少硬币数" + dp[i]);

//return dp[i];

}

return -1;

}

/****************************** ******************************/

结束写代码

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int res;

int _prices_size = 0;

_prices_size = Integer.parseInt(in.nextLine().trim());

int[] _prices = new int[_prices_size];

int _prices_item;

for (int _prices_i = 0; _prices_i < _prices_size; _prices_i++) {

_prices_item = Integer.parseInt(in.nextLine().trim());

_prices[_prices_i] = _prices_item;

}

int _budget;

_budget = Integer.parseInt(in.nextLine().trim());

res = solution(_prices, _budget);

System.out.println(String.valueOf(res));

}

}