//原来的答案 算法复杂度太大 空间复杂度也大 //参考讨论区的 更新 新方法 import java.util.Scanner; import java.util.Arrays; public class Main{ public static long count(int n){ if(n <= 0)return 0; int[] coins = new int[]{1,5,10,20,50,100}; long[] dp = new long[n+1]; dp[0] = 1; for(int i = 0; i < coins.length; i++) { for(int j = coins[i]; j <= n; j++) { dp[j] = dp[j] + dp[j - coins[i]];//类似斐波那契 后者的种类数基于前者 } } return dp[n]; } public static void main(String args[]){ Scanner sc=new Scanner(System.in); while(sc.hasNext()){ int n=sc.nextInt(); long res=count(n); System.out.println(res); } } }
//原方法import java.util.Scanner;
import java.util.Arrays;
public class Main{
public static long count(int n){
int coins[]={1,5,10,20,50,100};
int h=coins.length;
long dp[][]=new long[h][n+1];
Arrays.fill(dp[0], 1);//基础 该数字都由1组成 方法数是1
for(int i=1;i<h;i++){
for(int j=1;j<=n;j++){
int m=j/coins[i];
for(int k=0;k<=m;k++){
dp[i][j]=dp[i][j]+dp[i-1][j-k*coins[i]];
}
}
}return dp[h-1][n];}
#include<iostream> using namespace std; int main(){ int N = 0; cin >> N; long long * F = new long long[N + 1](); int c[6] = { 1, 5, 10, 20, 50, 100 }; F[0] = 1; for (int i = 0; i < 6; i++) for (int v = c[i]; v <= N; v++){ F[v] = F[v] + F[v - c[i]]; } cout << F[N]<<endl; return 0; }
import java.util.Scanner; public class Coins { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int amount = sc.nextInt();// 总钱数 int[] price = { 1, 5, 10, 20, 50, 100 };// 货币面值 // fun(price, amount); fun2(price, amount); } } //方法一: public static void fun1(int[] price, int amount) { long[][] matrix = new long[price.length][amount + 1]; for (int i = 0; i < amount + 1; i++) { matrix[0][i] = 1; } for (int i = 0; i < price.length; ++i) { matrix[i][0] = 1; } for (int i = 1; i < price.length; ++i) { for (int j = 1; j < amount + 1; ++j) { matrix[i][j] += matrix[i - 1][j]; if (j - price[i] >= 0) { matrix[i][j] += matrix[i][j - price[i]]; } } } System.out.println(matrix[price.length - 1][amount]); } //方法二: //每一个中间状态只会被用到一次,所以可以重复利用一维数组 public static void fun2(int[] price, int amount) { long[] array = new long[amount + 1]; for (int i = 0; i < array.length; ++i) { array[i] = 1; } for (int j = 1; j < price.length; ++j) { for (int k = 1; k < array.length; ++k) { if (k - price[j] >= 0) { array[k] += array[k - price[j]]; } } } System.out.println(array[amount]); } }
n=int(raw_input()) c=[1,5,10,20,50,100] methods=[[0 for i in range(n+1)] for j in range(6)] for i in range(6): methods[i][0]=1 for j in range(n+1): methods[0][j]=1 for i in range(1,6): for j in range (1,n+1): if j>=c[i]:"""这里是指在使用前i种钱币时,只有j>=第i种钱币时,使用前i种钱币找j元钱的方法methods[i][j]才会改变,否则和使用前i-1种钱币组成j元钱的方法相同""" methods[i][j]=methods[i-1][j]+methods[i][j-c[i]] else: methods[i][j]=methods[i-1][j] print methods[5][n]
#include<iostream> using namespace std; int main() { int n; cin>>n; int coin[6]={1,5,10,20,50,100}; long** dp = new long* [7]; for(int i=0; i<7; ++i) dp[i] = new long[n+1]; for(int i=0; i<7; ++i) dp[i][0] = 1; for(int i=0; i<=n; ++i) dp[0][i] = 0; for(int i=1; i<7; ++i) { for(int j=1; j<=n; ++j) { if(j-coin[i-1]>=0) dp[i][j] = dp[i-1][j]+dp[i][j-coin[i-1]]; else dp[i][j] = dp[i-1][j]; } } cout<<dp[6][n]<<endl; return 0; }
N=input('') N=int(N) penny=[1,5,10,20,50,100] matrix = [[0 for i in range(6)] for j in range(N+1)] matrix[0]=[1,1,1,1,1,1] for i in range(N+1): matrix[i][0]=1 for j in range(1,6): if i-penny[j]>0: matrix[i][j]=sum(matrix[i-penny[j]][0:j+1]) if (i-penny[j])==0: matrix[i][j]=1 print(sum(matrix[i][:]))
//参照大神:昵称真难区的 //版本:自顶向下的备忘录递归解法 #include <iostream> long count(int type, int money); int price[7] = { 0, 1, 5, 10, 20, 50, 100 }; long amount[7][10000 + 1]; int main() { for (int i = 0; i <= 10000; i++) { amount[1][i] = 1; } for (int i = 2; i < 7; i++) { for (int j = 0; j <= 10000; j++) { amount[i][j] = 0; } } int n; std::cin >> n; std::cout << count(6, n); //system("pause"); } long count(int type, int money) { if (type == 1) { return amount[0][money]; } else { for (int i = 0; i <= money / price[type]; i++) { int m = money - i*price[type]; if (amount[type-1][m] != 0) { amount[type][money] += amount[type-1][m]; } else { amount[type][money] += count(type-1, m); } } return amount[type][money]; } }
//动态规划,注意用来存储结果的dp必须为8字节长整型, //在我的windows系统中,long是4字节,long long是8字节;而linux上long就是8字节, //牛客网判题机应该是linux系统,因此long就可以过,这点要注意一下 #include <iostream> #include <vector> using namespace std; long long coinCombination(int* coins,int kindsOfcoins,int sum) { vector<vector<long long>> dp(kindsOfcoins,vector<long long>(sum+1,0)); for(int i=0;i<kindsOfcoins;++i) dp[i][0]=1; for(int i=0;i<=sum;i+=coins[0]) dp[0][i]=1; for(int i=1;i<kindsOfcoins;++i) { for(int j=1;j<=sum;++j) { for(int k=0;j-k*coins[i]>=0;++k) { dp[i][j]+=dp[i-1][j-k*coins[i]]; } } } return dp[kindsOfcoins-1][sum]; } int main() { int coins[6]={1,5,10,20,50,100}; int sum; while(cin>>sum) { long long result=coinCombination(coins,6,sum); cout<<result<<endl; } return 0; }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.Arrays; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String strN; while((strN = br.readLine()) != null){ int N = Integer.parseInt(strN); System.out.println(solve(N)); } } private static long solve(int N) { if(N == 0) return 0; int[] value = {1, 5, 10, 20, 50, 100}; long[] dp = new long[N + 1]; Arrays.fill(dp, 1); for(int vidx = 1; vidx < 6; vidx++){ for(int money = 1; money <= N; money++){ if(money >= value[vidx]) dp[money] += dp[money - value[vidx]]; } } return dp[N]; } }
// 动态规划分硬币
#include<iostream> using namespace std; long long dp(int n){ int base[]={1,5,10,20,50,100},m=6; long long F[n+1]; for(int i=0;i<n+1;i++)F[i]=1; for(int i=1;i<m;i++){ for(int j=base[i];j<n+1;j++){ F[j]=F[j]+F[j-base[i]]; } } return F[n]; } int main() { int n; while(cin>>n){ cout<<dp(n)<<endl; } return 0; }
#include <iostream> #include <string> #include <vector> #include <algorithm> int main() { using namespace std; int n; while (cin >> n) { int arr[] = { 1, 5, 10, 20, 50, 100 }; int rows = sizeof(arr) / sizeof(arr[0]); vector<vector<long long> > dp(rows, vector<long long>(n+1, 0)); for (int i = 0; i <= n; i++) { dp[0][i] = 1; } for (int i = 1; i < rows; i++) { for (int j = 0; j <= n; j++) { int m = j / arr[i]; for (int k = 0; k <= m; k++) { dp[i][j] = dp[i][j] + dp[i - 1][j - k * arr[i]]; } } } cout << dp[rows - 1][n] << endl; } return 0; }参考大神: 昵称真难取 的程序。
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.println(getTotal(scanner.nextInt())); } private static long getTotal(int money) { long total = 0L; for (int num = 0; num <= money; num += 50) { // 求解 100x + 50y = num 非负整数解的个数 int z1 = (num / 50) / 2 + 1; int v20 = (money - num) / 20; for (int k = 0; k <= v20; k++) { // 求解 10x + 5y <= v1andv5andV10 非负整数解的个数 int v1andv5andV10 = money - num - 20 * k; int tmp = (v1andv5andV10 / 5); long kkkk = tmp / 2 + 1; long z2 = (tmp + 2-kkkk) * kkkk; total = total + z1 * z2; } } return total; } }
[编程题]大富翁游戏
[编程题]拼凑钱币
[编程题]最大矩形面积
[编程题]最长公共连续子串
动态规划求解
import java.util.Scanner; import java.util.Arrays; public class Main { int M[]={5,10,20,50,100}; public static void main(String[] args){ Main s=new Main(); int n = (new Scanner(System.in)).nextInt(); long dp[] = new long[n+1]; Arrays.fill(dp, 1); for(int m:s.M){ for(int j=m;j<=n;j++){ dp[j]+=dp[j-m]; } } System.out.println(dp[n]); } }
Python
可参考leatcode上的解答,用python代码进行实现,原解答链接为:https://leetcode.com/problems/coin-change-2/discuss/99210/python-O(n)-space-dp-solution
# -*- coding:utf8 -*-
def split_money(n):
money = [1, 5, 10, 20, 50, 100]
dp = [0] * (n + 1)
dp[0] = 1
for i in money:
for j in range(1, n+1):
if j >= i: dp[j] += dp[j-i]
return dp[n]
print(split_money(eval(input())))