不知道动态规划是啥，搜索到这篇动态规划算法（DP）
现在把java版的动态规划理解记录一下
题目描述
给你六种面额1、5、10、20、50、100元的纸币，假设每种币值的数量都足够多，编写程序求组成N员（N为0-10000的非负整数）的不同组合的个数。
输入描述:
输入为一个数字N，即需要拼凑的面额
输出描述:
输出也是一个数字，为组成N的组合个数。
首先要有一个DP表格的想法
单元格的值 为当前金额，用当前拥有货币的组合方法
比如那个加粗的 4 的意思是 用{1 5 10} 3种货币 有4种组合方式可以组合成10元
//定义拥有的币种int[] money = {1, 5, 10, 20, 50, 100};//需要组成的金额int n = 10;//存储行的组合次数int[] li = new int[n + 1];//设定初始值li[0] = 1;//拿到当前拥有最大金额for (int m : money) {//遍历需要组合的金额for (int i = 1; i <= n; i++) {//如果当前金额可以组成if (i >= m) {// i-m =（当前金额-需要组合金额）//li[i-m] = （当前金额-需要组合金额）组合的需要次数//li[i] = 上一次的组合总次数 + （当前金额-需要组合金额）金额 组合的需要次数//用加粗的4解释就是 4 = 3+1;//3 = DP[5][10] //1 = DP[5][0] li[0]默认为1li[i] = li[i] + li[i - m];}}}
完整版代码
跑两遍就很直观了
public class Main {public static void main(String[] args) {//定义拥有的币种int[] money = {1, 5, 10, 20, 50, 100};//需要组成的金额int n = 10;//存储行的组合次数int[] li = new int[n + 1];//设定初始值li[0] = 1;//输出X轴值 （需要合成的金额）System.out.printf("%4d | ", 0);for (int i = 1; i < n + 1; i++) {System.out.printf("%4d", i);}//为了美观。。。。没有意义System.out.println();for (int i = 0; i < n + 2; i++) {System.out.printf("%4s", "——");}System.out.println();for (int m : money) {//输出Y轴坐标轴值 （拥有金额）System.out.printf("%4d | ", m);for (int i = 1; i <= n; i++) {if (i >= m) {li[i] = li[i] + li[i - m];}}sout(li);}}//输出当前组合值private static void sout(int[] li) {for (int i = 1; i < li.length; i++) {System.out.printf("%4d", li[i]);}System.out.println();}}
