今天在leetcode上做了幾道dynamic programming的題型型。就其中兩道題做個總結(jié)吧勋拟。
Coin change
先從第一道題講起历筝，題目大意是：有不同面值的硬幣掖蛤，以及一個需要由各種硬幣組成的數(shù)字毡鉴，需要找出最少要幾個硬幣才能組成這個數(shù)字石挂。（每種面值的硬幣的數(shù)量都是無窮的）博助。如果硬幣無法組成這個數(shù)字，返回-1痹愚。
這是一個例子富岳，下面的講解也用這個例子：
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
這是一個一眼看上去就比較典型的dp問題，我直觀地想到的解法就是
1. 直接使用recursion方法
一開始拯腮，我直接使用上面這個總結(jié)出來的公式城瞎，寫出了如下代碼，顯然是不符合時間復(fù)雜度的疾瓮。但是可以作為優(yōu)化的起點。
class Solution {
public int coinChange(int[] coins, int amount) {
//f(n) = 1 + min(f(n-1), f(n-5), f(n-10))
// 1 5 10 is type of coin
if(amount == 0) {
return 0;
}
int res = Integer.MAX_VALUE;
for(int coin: coins) {
if(amount - coin >= 0) {
res = Math.min(res, coinChange(coins, amount-coin));
}
}
return (res == Integer.MAX_VALUE || res < 0)?-1:res+1;
}
}
2. 優(yōu)化recursion方法
根據(jù)前面一篇dynamic programming文章提到的飒箭，對recursion進(jìn)行優(yōu)化狼电，可以用一個array將已經(jīng)計算過的東西儲存起來，避免重復(fù)運算弦蹂。
class Solution {
public int coinChange(int[] coins, int amount) {
if(amount == 0) {
return 0;
}
int[] cache = new int[amount+1];
Arrays.fill(cache, -1);
for(int coin: coins) {
if(coin <= amount) {
cache[coin] = 1;
}
}
return coinChange(coins, amount, cache);
}
public int coinChange(int[] coins, int amount, int[] cache) {
if(cache[amount] >= 0) {
return cache[amount];
}
int res = Integer.MAX_VALUE;
for(int coin: coins) {
if(amount-coin >= 0) {
res = Math.min(res, coinChange(coins, amount-coin, cache));
}
}
cache[amount] = (res == Integer.MAX_VALUE || res < 0)?-1:res+1;
return cache[amount];
}
}
優(yōu)化過的recursion代碼思想還是和之前的一致的肩碟，只是增加了cache變量。
3. 將從上到下轉(zhuǎn)化為從下到上
Dynamic programming最重要的一步凸椿。之前的recursion代碼是從上到下的一個過程削祈，在這一步需要將它轉(zhuǎn)化為從下到上，去除recursion過程，因為recursion往往會需要更多的space髓抑。
下面是代碼
class Solution {
public int coinChange(int[] coins, int amount) {
if(amount == 0) {
return 0;
}
int[] cache = new int[amount+1];
Arrays.fill(cache, -1);
for(int coin: coins) {
if(coin <= amount) {
cache[coin] = 1;
}
}
for(int i = 1; i <= amount; i++) {
if(cache[i] >= 0) {
continue;
} else {
int res = Integer.MAX_VALUE;
for(int coin: coins) {
if(i-coin >= 0 && cache[i-coin]!=-1) {
res = Math.min(res, cache[i-coin]+1);
}
cache[i] = (res==Integer.MAX_VALUE||res<=0)?-1:res;
}
}
}
return cache[amount];
}
}
之后在discussion看到了更加簡潔的答案：
public class Solution {
public int coinChange(int[] coins, int amount) {
int max = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, max);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
總結(jié)
從整體的解答思想和一步一步得到danamic programming解法的過程來說咙崎，我的解答完全遵循前面一篇文章中提到的步驟。我在解題過程中遇到的最大的問題不是代碼的邏輯吨拍，而是edge case的處理和array的initial value褪猛，其實這兩個是同一個問題。我做了很多種不同的嘗試羹饰，但是最后都沒有寫出和討論區(qū)看到的解答那樣簡潔的答案伊滋。
通過學(xué)習(xí)別人的代碼，我學(xué)習(xí)到的：根據(jù)迭代的方法設(shè)立好的初始值對edge case來說至關(guān)重要队秩。但是還沒能總結(jié)出什么規(guī)律笑旺，還需要多學(xué)習(xí)別人的解答。不要總盯著0馍资，1筒主，-1，Integer.MAX_VALUE迷帜，Integer.Min_VALUE不放物舒。
