青岛网页建站模板网站制作的费用

一、题目

题目描述有数量不限的硬币，币值为25分、10分、5分和1分，请编写代码计算n分有几种表示法。给定一个int n，请返回n分有几种表示法。保证n小于等于100000，为了防止溢出，请将答案Mod 1000000007。
测试样例：6返回：2

二、分析

这一题和完全背包几乎一模一样，每种硬币都是数量不限的，设dp[i][j]为使用第i种硬币来表示j分时表示法有dp[i][j]种，A[i]是第i种硬币的价值。
在使用第i种硬币表示j分时有两种情况:
1、A[I]<=j，此时dp[i][j]=dp[i-1][j]+dp[i][j-A[i]];
意思是：在第i种硬币的价值小于j分,此时可以选择使用或者不用第i种硬币,如果不使用则为dp[i-1][j],使用了则是dp[i][j-A[i]]，因此应该为两种情况之和。
2、A[i]>j,此时dp[i][j]=dp[i-1][j];

背包问题链接:http://blog.csdn.net/xiaofengcanyuelong/article/details/79323104

public class YingBiBiaoShi {public static void main(String[] args) {System.out.println(countWays(6));}public static int countWays(int n) {int A[] = { 1, 5, 10, 25 }, dp[][] = new int[A.length][n + 1];for (int j = 0; j <= n; j++) {dp[0][j] = 1;//初始化}for (int i = 1; i < A.length; i++) {for (int j = 0; j <= n; j++) {if (A[i] <= j) {dp[i][j] = (dp[i - 1][j] + dp[i][j-A[i]]) % 1000000007;} else {dp[i][j] = dp[i - 1][j];}}}return dp[A.length - 1][n];}
}

三、优化

使用一维滚动数组来表示。

public static int countWays2(int n) {int c[] = new int[n + 1];c[0] = 1;int a[] = { 1, 5, 10, 25 };for (int i = 0; i < a.length; i++) {for (int j = 0; j < n + 1; j++) {if (a[i] <= j) {c[j] = (c[j] + c[j - a[i]]) % 1000000007;}}}return c[n];}

Every day is a new start。