力扣labuladong一刷day59天动态规划
一、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[amount+1];
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];
}
}
