力扣labuladong一刷day59天動態(tài)規(guī)劃

一、509. 斐波那契數(shù)

題目鏈接：https://leetcode.cn/problems/fibonacci-number/description/
思路：這是非常典型的一道題，下面是優(yōu)化過的代碼，a,b就是dp數(shù)組，因?yàn)槊坑嬎阋粋€值，需要前兩個值，這個a,b就是用來記錄前兩個值，避免重復(fù)計算，遞推公式便是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/
思路：本題是一個典型完全背包問題，物品數(shù)量無限，故物品在外，背包在內(nèi)，均正序，背包正序用來滿足物品無限。
定義dp數(shù)組，dp[j]表示要填滿容量為j的背包所需要的最少物品數(shù)量。
遞推公式為dp[j] = min(dp[j-coins[i]] + 1, dp[j])，求最少物品數(shù)量，有兩種選擇，要么是放入當(dāng)前物品，要么是不放入當(dāng)前物品。放入的話，自然就是剛好少于當(dāng)前物品值的容積所對應(yīng)的物品數(shù)量加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];}
}