广西网站建设软件推广,门户网站制作公司,建设大型网站制作品牌,做网站499力扣labuladong一刷day59天动态规划 文章目录 力扣labuladong一刷day59天动态规划一、509. 斐波那契数二、322. 零钱兑换 一、509. 斐波那契数
题目链接#xff1a;https://leetcode.cn/problems/fibonacci-number/description/ 思路#xff1a;这是非常典型的一道题#x…力扣labuladong一刷day59天动态规划 文章目录 力扣labuladong一刷day59天动态规划一、509. 斐波那契数二、322. 零钱兑换 一、509. 斐波那契数
题目链接https://leetcode.cn/problems/fibonacci-number/description/ 思路这是非常典型的一道题下面是优化过的代码a,b就是dp数组因为每计算一个值需要前两个值这个a,b就是用来记录前两个值避免重复计算递推公式便是f(n) f(n-1)f(n-2)。
class Solution {public int fib(int n) {if (n 2) return n;int a 0, b 1, c 0;for (int i 2; i n; i) {c a b;a b;b c;}return b;}
}二、322. 零钱兑换
题目链接https://leetcode.cn/problems/coin-change/description/ 思路本题是一个典型完全背包问题物品数量无限故物品在外背包在内均正序背包正序用来满足物品无限。 定义dp数组dp[j]表示要填满容量为j的背包所需要的最少物品数量。 递推公式为dp[j] min(dp[j-coins[i]] 1, dp[j])求最少物品数量有两种选择要么是放入当前物品要么是不放入当前物品。放入的话自然就是刚好少于当前物品值的容积所对应的物品数量加1不放入的话直接使用dp[jj]的值该dp[j]可能由之前的物品所填满也有可能还没填。
class Solution {public int coinChange(int[] coins, int amount) {int[] dp new int[amount1];Arrays.fill(dp, Integer.MAX_VALUE);dp[0] 0;for (int i 0; i coins.length; i) {for (int j coins[i]; j dp.length; j) {if (dp[j - coins[i]] ! Integer.MAX_VALUE) {dp[j] Math.min(dp[j-coins[i]] 1, dp[j]);}}}return dp[amount] Integer.MAX_VALUE ? -1 : dp[amount];}
}
