seo网站优化服务_西安小程序开发哪家好_百度移动点击排名软件_搜索网站的浏览器

解法一：（动态规划）①定义：dp[i]表示能组合成i的最少硬币个数，dp[n+1] ②初始状态：dp[0]=0 dp[i]=Integer.MAX_VALUE ③状态转移方程：dp[i] = Math.min(min, dp[i - j*j])+1，因为每次循环都i++，之前的最小完全平方数加起来肯定不能到i，所以min必须+1

import java.util.*;/*** @author longyy* @version 1.0*/
class Solution79 {
public int coinChange(int[] coins, int amount) {// 定义：dp[i]表示能组合成i的最少硬币个数，dp[n+1]// 初始状态：dp[0]=0 dp[i]=Integer.MAX_VALUE// 状态转移方程：dp[i] = Math.min(min, dp[i - j*j])+1，因为每次循环都i++，之前的最小完全平方数加起来肯定不能到i，所以min必须+1int[] dp = new int[amount + 1]; // dp[i]表示得到和为i的最少硬币个数Arrays.fill(dp, Integer.MAX_VALUE);dp[0] = 0;for (int i = 1; i <= amount; i++) {// i++，i变大了，每次都尝试从硬币中找一个数加进去int min = Integer.MAX_VALUE;for (int j = 0; j < coins.length; j++) {if (coins[j] <= i && dp[i - coins[j]]!=Integer.MAX_VALUE) {// 找到了min = Math.min(min,dp[i - coins[j]]+1);}// if (coins[j] <= i) {//     min = Math.min(min, dp[i - coins[j]]==Integer.MAX_VALUE?Integer.MAX_VALUE:dp[i - coins[j]]+1);// }dp[i] = Math.min(dp[i], min);}}if(dp[amount] == Integer.MAX_VALUE){return -1;}return dp[amount];}public static void main(String[] args) {Scanner in = new Scanner(System.in);String s = in.nextLine().trim();int amount = in.nextInt();String[] split = s.split(",");int[] coins = new int[split.length];for (int i = 0; i < split.length; i++) {coins[i] = Integer.parseInt(split[i]);}Solution79 sol = new Solution79();System.out.println(sol.coinChange(coins, amount));}
}

注意：

• 为了方便后续判断，Arrays.fill(dp, Integer.MAX_VALUE);
• Math.min(min, dp[i - coins[j]]==Integer.MAX_VALUE?Integer.MAX_VALUE:dp[i - coins[j]]+1) 取到这个数之前，要判断这个数是否为Integer.MAX_VALUE，如果是的话，这个数不可取。
• dp初始化为dp[n+1]，初始状态为Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0;，返回值为dp[n]
• 初始化dp数组大小时，一般计算总数时是n+1；其余为n