[Leedcode][JAVA][面试题 08.11][硬币][动态规划]

【问题描述】 面试题 08.11.硬币

硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)示例1:输入: n = 5输出：2解释: 有两种方式可以凑成总金额:5=55=1+1+1+1+1

【解答思路】

1. 动态规划 二维数组

1.1 令 dp[i][j] 为遍历到当下这个硬币时，组成金额 j 的方法数目

1.2 有两种可能性

（1）当前这个硬币没有取，dp[i][j]=dp[i-1][j]；

（2）当前这个硬币取了，dp[i][j]=dp[i][j-coins[i]]。最后的结果是两者的和

1.3 将状态转移方程翻译成代码，并处理边界条件

时间复杂度：O(NM) 空间复杂度：O(NM)

N ：金额 M：硬币类型

class Solution {public int waysToChange(int n) {if (n < 5)return 1;if (n == 5)return 2;int[] coins = {1, 5, 10, 25};int[][] dp = new int[4][n + 1];// 当数量为0，1时，有1种表示法for(int i = 0; i < 4; ++i){dp[i][0] = 1;dp[i][1] = 1;} // 当只有一种硬币时，只有1种表示法for(int i = 0; i <=n; ++i)dp[0][i] = 1;/** 状态：dp[i][j]表示[0...i]种硬币能组合为j的所有不同种数* 状态转移：取 或 不取 当前硬币coins[i]*/for (int i = 1; i < 4; ++i) {for (int j = 2; j <= n; ++j) {if (j >= coins[i])dp[i][j] = (dp[i][j - coins[i]] + dp[i - 1][j]) % 1000000007;elsedp[i][j] = dp[i - 1][j];}}return dp[3][n];}}

2. 动态规划优化 一维数组

从上面的状态转移方程可以看出，dp[i][j]只与dp[i-1][j]和dp[i][j-coins[i]]有关，所以完全可以把第一个维度除掉，只用一个一维数组存储

时间复杂度：O(MN) 空间复杂度：O(N)

N ：金额 M：硬币类型

public int waysToChange2(int n) {int[] dp=new int[n+1];int[] coins={1,5,10,25};for(int i=0;i<=n;i++)dp[i]=1;for(int i=1;i<4;i++){for(int j=1;j<=n;j++){if(j>=coins[i])dp[j]=(dp[j]+dp[j-coins[i]])%1000000007;}}return dp[n];}

【总结】

1. 动态规划流程

第 1 步：设计状态

第 2 步：状态转移方程

第 3 步：考虑初始化

第 4 步：考虑输出

第 5 步：考虑是否可以状态压缩

2. 数组初始化

一维数组

1.在定义时初始化。

int[] arrays = {1, 2, 3, 4, 5};//简化int[] arrays = new int[]{1, 2, 3, 4, 5};//完整格式 推荐

2.先定空间，随后赋值。

- int []age = new int[10];//动态初始化for (int i = 0; i < age.length; i++) {age[i] = i;}

二维数组

1.在定义时初始化。

double[][] a = new double[][] {{1,2,3},{4,2,7}};double[][] b = new double[][] {{3,3},{1,1},{2,2}};2.先定空间，随后赋值。

double [][] container = new double[3][4];

for(int i = 0; i < 3;i++) {

for(int j = 0; j < 4;j++) {

container[i][j] = 4.5;

}

}

3.DFS 全排思想（顺序有关） 不可以 无序方案

n = 6 时 ，输出次数3（实际2）1 1 1 1 1 15 11 5（重复）

private int[] money = new int[]{1,5,10,25}; private int count = 0;public int waysToChange(int n) {if(n<5){return 1;}int i=0;conutSort(i,n);return count;}void conutSort(int i,int n){if(i>n){return ;}if(i==n){count++;count = count % 1000000007;}if(i <n){for(int j= 0 ;j<4;j++){conutSort( money[j]+i, n);}}}

参考链接：https://leetcode-/problems/coin-lcci/solution/dong-tai-gui-hua-jian-dan-yi-dong-by-yuanninesuns/