网站仿做,安徽建讯建设工程管理有限公司,wordpress 焦点图大小,wordpress教程阿里云文章目录 1、记忆化搜索2、leetcode509#xff1a;斐波那契数列3、leetcode322#xff1a;零钱兑换 1、记忆化搜索
也叫备忘录#xff0c;即把已经计算过的结果存下来#xff0c;下次再遇到#xff0c;就直接取#xff0c;不用重新计算。目的是以减少重复计算。 以前面提… 文章目录 1、记忆化搜索2、leetcode509斐波那契数列3、leetcode322零钱兑换 1、记忆化搜索
也叫备忘录即把已经计算过的结果存下来下次再遇到就直接取不用重新计算。目的是以减少重复计算。 以前面提到的斐波那契数列为例计算F(5)拆成F(4) F(3)接下来递归的顺序如上图红色箭头会先算左侧一支计算完F(4)后函数往下接着执行才计算右侧一支的F(3) 可以发现计算左侧一支的F(4)时会得到F(3)的值存下F(3)的值的话执行到右侧一支计算F(3)时直接取就行。 考虑初始化一个数组数组元素为一个题目中不可能出现的值。然后将F(0)存在数组下标为0的地方F(3)存数组下标为3的地方计算一个值时先在数组中找找不到时再计算。
2、leetcode509斐波那契数列 用一个int数组存储计算过的每个F(x)方便后面使用
public class P509Two {public int recursion(int n) {//F(0)和F(1)if (n 2) {return n 0 ? 0 : 1;}int[] dp new int[n 1];dp[1] 1; //F(1)// 根据方程式计算每个值存入数组从F(2)一路计算到F(5)for (int i 2; i n; i) {dp[i] dp[i - 1] dp[i - 2];}return dp[n];}
}
当然这儿也是动态规划。至于二者的在这块儿的区别参考前一篇的爬楼梯那题。动态规划重在状态转移那些不用的中间值存不存在你。记忆化搜索则重在存储已计算结果的方式来避免重复计算。 3、leetcode322零钱兑换 总金额amount恰好等于硬币面值时最优解为1 考虑利用等于硬币面值金额的最优解推出其他金额的最优解。选择一个面值小于 总金额amount 的硬币之后剩余金额对应的最优解是已知的选择这些剩余金额最优解中最小的再加上对应的那张面值小于i 的硬币就是总金额amount的最优解。 如上amount 3面值小于amount的硬币有面值为1和面值为2的
如果选择面值为1的剩余3 - 1 2而2的最优解就是1那amount的最优解就是 1 1 2如果选择面值为2的剩余3 - 2 1而1的最优解就是1那amount的最优解就是 1 1 2
因此amount的最优解是2。如此amount 已知面值时也可以这样推出来比如amount 2。同理 amount 14的剩余金额中剩余7时最优解最小为1因此14最优解就是 1 1 2。以amount14为例初始化一个amount 1的dp数组 根据上面的分析14有五种写法选择最小值返回即可 假设硬币面值有c1、c2、c3那动态规划的状态转移方程式为
F(amount) MinF(amount - c1) F(amount - c2) F(amount - c3) 1有点像动态规划-完全平方数那题。实现动态规划
public class P322 {public int coinChange(int[] coins, int amount) {if (null coins || coins.length 0) {return 0;}int[] dp new int[amount 1];// 填充-1Arrays.fill(dp, -1);// 金额0的最优解dp[0] 0;for (int i 1; i amount; i) {// 对于每个金额i遍历面值集合coinsfor (int coin : coins) {// 如果面值小于等于总金额i并且剩余金额有最优解if (coin i dp[i - coin] ! -1) {// 如果总金额i没有计算过或者总金额i的最优解比正在计算的最优解大if (dp[i] -1 || dp[i] dp[i - coin] 1) {// 更新最优解dp[i] dp[i - coin] 1;}}}}return dp[amount];}
}
