1）输入最大情况100000 ，本地IDE运行时间大概在 2093毫秒，在线编辑器要求在3秒内，但是总是提示超时 /** * 硬币表示 * 题目描述：4种硬币，币值分别为 1 5 10 25 给定n，使用这些币种来表示n，求最对的表示方法 * 思路完全套用0-1背包问题，动态规划 * 讨论使用到第i种币表示j分时，能够表示的最多方法数量，涉及到2个自变量，使用二维数组维护讨论结果maxN[i][j] * 递推公式 * maxN[0][j] = 0 * maxN[i][0] = 1 * maxN[1][j] = 1 * maxN[i][j] = * { * 1) maxN[i-1][j] (j < coins[i]) * 2) maxN[i-1][j] + Sum{ maxN[i-1][j-k*coins[i]]| 1<=k<=j/coins[i] } (j >= coins[i]) 使用coins[i] 和不使用coins[i]所有情况的总和 * } */ package dp; import java.util.Scanner; public class Main { static int[] coins = {0, 1, 5, 10, 25}; static int[][] maxN = null; public static void main(String[] args){ Scanner in = new Scanner(System.in); int n = in.nextInt(); System.out.println(countWays(n)); for(int i = 1; i <= 4; i++){ for( int j = 1; j <= n; j++){ System.out.print(maxN[i][j]+" "); } System.out.println(""); } } public static int countWays(int n) { if(n < 1) return 0; maxN = new int[coins.length][n+1]; for(int j = 1; j<= n; j++){ maxN[1][j] = 1; } for(int i = 1; i <= 4; i++){ maxN[i][0] = 1; } for(int i = 2; i <= 4; i++){ for(int j = 1; j <= n; j++){ if(j < coins[i]) maxN[i][j] = maxN[i-1][j]; else{ int temp = 0; for(int k = j/coins[i]; k >= 1; k--){ temp += maxN[i-1][j-k*coins[i]]; } maxN[i][j] = maxN[i-1][j] + temp; } } } return maxN[4][n]; } } 2）优化了一下，将循环改掉就可以了，循环存在这大量的重复计算 /** * 硬币表示 * 题目描述：4种硬币，币值分别为 1 5 10 25 给定n，使用这些币种来表示n，求最对的表示方法 * 思路完全套用0-1背包问题，动态规划 * 讨论使用到第i种币表示j分时，能够表示的最多方法数量，涉及到2个自变量，使用二维数组维护讨论结果maxN[i][j] * 递推公式 * maxN[0][j] = 0 * maxN[i][0] = 1 * maxN[1][j] = 1 * maxN[i][j] = * { * 1) maxN[i-1][j] (j < coins[i]) * 2) maxN[i-1][j] + Sum{ maxN[i-1][j-k*coins[i]]| 1<=k<=j/coins[i] } (j >= coins[i]) 使用coins[i] 和不使用coins[i]所有情况的总和 * } */ package dp; import java.util.Date; import java.util.Scanner; public class Main { static int[] coins = {0, 1, 5, 10, 25}; static int[][] maxN = null; public static void main(String[] args){ Scanner in = new Scanner(System.in); int n = in.nextInt(); long t1 = new Date().getTime(); System.out.println(countWays(n)); System.out.println(new Date().getTime() - t1); } public static int countWays(int n) { if(n < 1) return 0; maxN = new int[coins.length][n+1]; for(int j = 1; j<= n; j++){ maxN[1][j] = 1; } for(int i = 1; i <= 4; i++){ maxN[i][0] = 1; } for(int i = 2; i <= 4; i++){ for(int j = 1; j <= n; j++){ if(j < coins[i]) maxN[i][j] = maxN[i-1][j]; else{ // int temp = 0; // for(int k = j/coins[i]; k >= 1; k--){ // temp += maxN[i-1][j-k*coins[i]]; // } // maxN[i][j] = maxN[i-1][j] + temp; maxN[i][j] = maxN[i-1][j] + maxN[i][j-coins[i]];//可以使用该币种但是不用的表示方法数为当前分值下前一种状态 //币种能表示的种数 maxN[i-1][j], //但是如果使用该币种，表示至少使用一个该币，那么问题可以转化为最后coins[i]的分数 //由1个coins[i]表示，即已经使用1个coins[i]的前提下，j-coins[i]分数可以由前i种币表示多少种分法？即maxN[i][j-coins[i]] } } } return maxN[4][n]; } }
