自己建网站 wordpress,镇江网站优化推广,网站怎么做目录跳转,建网【问题描述】 面试题 08.11.硬币
硬币。给定数量不限的硬币#xff0c;币值为25分、10分、5分和1分#xff0c;编写代码计算n分有几种表示法。(结果可能会很大#xff0c;你需要将结果模上1000000007)示例1:输入: n 5输出#xff1a;2解释: 有两种方式可以凑成总金额:
55…【问题描述】 面试题 08.11.硬币
硬币。给定数量不限的硬币币值为25分、10分、5分和1分编写代码计算n分有几种表示法。(结果可能会很大你需要将结果模上1000000007)示例1:输入: n 5输出2解释: 有两种方式可以凑成总金额:
55
511111
【解答思路】
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];// 当数量为01时有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[] dpnew int[n1];int[] coins{1,5,10,25};for(int i0;in;i)dp[i]1;for(int i1;i4;i){for(int j1;jn;j){if(jcoins[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实际21 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(n5){return 1;}int i0;conutSort(i,n);return count;}void conutSort(int i,int n){if(in){return ;}if(in){count;count count % 1000000007;}if(i n){for(int j 0 ;j4;j){conutSort( money[j]i, n);}}}参考链接https://leetcode-cn.com/problems/coin-lcci/solution/dong-tai-gui-hua-jian-dan-yi-dong-by-yuanninesuns/
