import java.util.Scanner; public class Solution { int count = 0; int[] arr; public int calculateWays(int n) { arr = new int[n + 1]; return calculateWays1(n); } //记忆化搜索递归 private int calculateWays1(int n) { if (n < 0) throw new IllegalArgumentException("input wrong"); if (n == 0) return 0; if (n == 1) return 1; if (n == 2 || n == 3) return 2; if (n == 4 || n == 5 || n == 6 || n == 7 || n == 8 || n == 9) return n - 1; if (n == 10) return 11; if (arr[n] != 0) return arr[n]; int res = 0; res = Math.max(Math.max(calculateWays1(n - 1) + 1, calculateWays1(n - 2) + 2), Math.max(calculateWays1(n - 5) + 4, calculateWays1(n - 10) + 11)); arr[n] = res; return res; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("请输入钱数:"); int n = sc.nextInt(); Solution s = new Solution(); int sum = s.calculateWays(n); System.out.println(sum); } }接楼上动态规划法,这是对应的递归解法,思路就是不断递归的寻找比n小1,2,5,10分的组合数量加组成1,2,5,10分的组合数量的最大值,个人认为递归算法更容易理解,但会反复计算很多重复的子问题,所以引入了记忆化搜索减少了计算次数,总体来讲由于递归本身的开销会比动态规划大,但递归思想适应性更广,理解两种解法对解类似的题目会更有帮助。
public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); sc.close(); int coins[] = { 1, 2, 5, 10 }; count(coins, 0, n); System.out.println(numcount); } // 递归 static int numcount = 0; public static void count(int coins[], int index, int aim) { if (aim == 0) { numcount++; return; } if (index == 4) { return; } for (int i = 0; i * coins[index] <= aim; i++) { count(coins, index + 1, aim - i * coins[index]); } }
package aadatastructureandalgorithm.dp; import java.util.Scanner; /** * @description: * @author: * @time: 2019/8/14 20:59 */ public class CombinateCoins { int[] tempMost = null; int count; public CombinateCoins(int n) { if (n <= 0) { throw new IllegalArgumentException(""); } if (n > 10) { tempMost = new int[n + 1]; count = n + 1; } else { tempMost = new int[11]; count = 11; } tempMost[0] = 0; tempMost[1] = 1; tempMost[2] = 2; tempMost[3] = 2; tempMost[4] = 3; tempMost[5] = 4; tempMost[6] = 5; tempMost[7] = 6; tempMost[8] = 7; tempMost[9] = 8; tempMost[10] = 11; } //蛮力法 void combinateCoinsByBtute() { Scanner scanner = new Scanner(System.in); System.out.println("请输入钱数"); int n = scanner.nextInt(); int sum = 0; int count = 0; for (int i = 0; i <= n; i++) { for (int j = 0; j <= (n / 2); j++) { for (int k = 0; k <= (n / 5); k++) { for (int l = 0; l <= (n / 10); l++) { if ((i + j * 2 + k * 5 + l * 10) == n) { sum++; } } } } } System.out.println(sum); } //动态规划 int combinateCoinsByDp(int n) { CombinateCoins combinateCoins = new CombinateCoins(n); if (n <= 10) { return combinateCoins.tempMost[n]; } for (int i = 11; i <= n; i++) { int most = 0; for (int j = 1; j <= i / 2; j++) { int tempCount = tempMost[j] + tempMost[i - j]; if (most < tempCount) { most = tempCount; } tempMost[i] = most; } } return tempMost[n]; } public static void main(String[] args) { while (true) { Scanner scanner = new Scanner(System.in); System.out.println("请输入钱数"); int n = scanner.nextInt(); CombinateCoins combinateCoins = new CombinateCoins(n); System.out.println(combinateCoins.combinateCoinsByDp(n)); } } }
''' 思路:求出10的取值范围,在取出10的基础上,然后在剩下的部分求出5的取值范围, 进而在取出5的基础上,对剩下部分求出2的取值范围,ok次数到位了 ''' while True: try: n = int(input()) a10 = n//10 count = 0 se = set([])#验证此算***不会存在重复的情况。。。。通过获取最后集合的长度与count是一样的,没有重复 for i in range(0,a10+1): for j in range(0,(n-i*10)//5+1): temp = n-i*10-j*5 for k in range(0,temp//2+1): t2 = n-i*10-j*5-k*2 #print('10:',i,' 5:',j,' 2:',k,' 1:',t2,' 和:',i*10+j*5+k*2+t2) se.add(str(i)+','+str(j)+','+str(k)+','+str(t2)) count+=1 print(count) except: break
public: int timu(int target){ this->target = target; dfs(0); return count; } private: int count = 0; vector<int> v; int total = 0, target; int a[] = {1,2,5,10}; int dfs(int index){ if(total == target){ count++; } if(total > target) return; for(int i = index; i < 4; i++){ total += a[i]; v.push_back(a[i]); dfs(i); v.pop_back(); total -= a[i]; } }
import java.util.Scanner; /** * @author wufuqiang * @title: study11 * @projectName:wufuqiang_thread * @description: T0D0 * @created 2019-09-18 09:02 */ public class Main { // 计算 只含 5,2,1 public static long count5(long m){ long c = 0; for (long i = m/5;i > 0;i--){ c = c + (m - 5*i)/2; c = c + 1; } return c; } public static void main(String[] args) { Scanner in = new Scanner(System.in); long n = in.nextInt(); long num = 0; // 只有 1 long a = 1; // 只有1,2 必有2 long b = n/2; // 只有1,2,5 必有5 long c = 0; for (long i = n/5;i > 0;i--){ c = c + (n - 5*i)/2; c = c + 1; } // 只有1,2,5,10 必有10 long d = 0; for (long i = n/10;i > 0;i--){ // 判断能否含有5 if(n < 15){ d = a + (n-10)/2; break; }else { d = d + count5((n - 10*i)); //含521 d = d + (n - 10*i)/2; //含21 d = d + 1; //含1 } } num = (a + b + c + d)%1000000007; System.out.println(num); } }
import java.util.Scanner; public class Null { public static void main(String[]args){ Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] dp = new int[n+1]; dp[0] = 1; int[] coins = new int[]{1, 2, 5, 10}; for(int i = 0; i <coins.length; i++ ){ for(int j = coins[i]; j <= n; j++){ dp[j] +=dp[j-coins[i]]; } } System.out.println(dp[n]); } }
n=int(input()) a=[0,1,2,5,10] dp=[[0 for j in range(5)] for i in range(n+1)] for i in range(0,n+1): dp[i][1]=1 ###只用1硬币地话永远只有一种可能 for j in range(5): dp[0][j]=1 for i in range(1,n+1): for j in range(2,5): if i >=a[j]: dp[i][j]=dp[i-a[j]][j]+dp[i][j-1] else: dp[i][j]=dp[i][j-1] print(dp[n][4])
#include<iostream> using namespace std; int main(){ int n; cin>>n; long long count=0; for(int i=0;i<=n/10;i++){ for(int j=0;j<=(n-i*10)/5;j++){ if(count+(n-i*10-j*5)/2+1>=(1e9+7)) count=count+(n-i*10-j*5)/2+1-(1e9+7); else count+=(n-i*10-j*5)/2+1; } } cout<<count; return 0; }
def get_small_money_combination(n, coins): if min(coins) <= 0: raise ValueError("Coins with value %d not existing in this world") if n == 0: return 0 old_comb = [1] * (n + 1) new_comb = [0] * (n + 1) for i in coins[1:]: for j in range(n + 1): for k in range(j // i + 1): new_comb[j] += old_comb[j - k * i] old_comb, new_comb = new_comb, [0] * (n + 1) return old_comb[-1]状态转移方程为:
dp[i][m] = sum(dp[i-1][m-k*Vm] for k in range(0, m/Vm))其中 dp[i][m] 代表有前 i 种硬币组成数字 m 的组合数,Vm 是第 i 种硬币的面值,参见https://blog.csdn.net/wickedvalley/article/details/76279480
public void out(int n) { for (int i = 0; i <= n ; i++) { for (int j = 0; j <= n/2 ; j++) { for (int k = 0; k <= n/5; k++) { for (int m = 0; m <= n/10 ; m++) { if (i + 2 * j + 5 * k + 10 * m == n) { System.out.println("1分: " + i + " 2分:" + j + " 5分" + k + " 10分:" + m) } } } } } }
*/ int n=789;//输入值 int type=0; int sum=0; for (int i = 0; i < n; i++) { sum+=1; for (int j = 0; j <(n-i); j++) { sum+=2; for (int k = 0; k <(n-i-j); k++) { sum+=5; for (int l = 0; l <(n-i-j-k); l++) { sum+=10; if(sum==n){ type++; System.out.println("第"+type+"种:?"+i+"?"+j+"?"+k+"?"+l); } } } } }