一開始先發個牢騷好了
雖然說開履歷才不到一個禮拜，也還沒開始面試
不過依照以往的經驗，開始找之後就是信心要開始下滑的時候了
上網找了一些職缺，發現我想去的公司條件都要求好多，而且都一堆人在投
想想也是很正常的嘛，好公司大家都想進，進不進的去就看個人能力和造化了
與其在那邊覺得自己實力不夠，不如就從現在開始好好加強自己的能力吧
如果說寫網誌能夠促進自己學習，那就盡量寫吧~
今天這題是一個換錢的題目
給一個陣列表示有哪些幣值，然後給你一個數字
算出用哪一個方法可以用最少的硬幣數量湊出那個數字，然後回傳那個數量，舉例來說：
Input: coins =[1, 2, 5], amount =11Output:3Explanation: 11 = 5 + 5 + 1
如果連一種方式都湊不出來，回傳-1
今天這題略難一點
至少對我來說是啦...
如果沒什麼概念，大概完全不知道怎麼辦吧
Sol:
這題主要是要用到一種Dynamic Programming的概念
有興趣可以去google一下
大概的想法就是藉由記錄算出的結果，然後一直往目標去算，利用記錄的結果去算出目標
這樣可以減少過程中很多不必要計算
最簡單的例子... 像費伯納西數列就有點類似的概念
記住前一次算出來的數值，來計算現在要計算的數值，而不是每次都要從頭算
但是這題又比較不一樣，不只要記住前一次的結果，而是要記住前面全部的結果
因為沒有辦法知道會有什麼幣值，所以只能全部記住了
大概的code是這樣，附上註解：
int coinChange(vector<int>& coins, int amount) {
int dp[amount + 1]; // 初始化一個大小為amount+1的陣列，用來記錄每一個數值最少要用多少硬幣組成
dp[0] = 0; // 0就是0
for (int i = 1; i <= amount; ++i)
{
dp[i] = -1; // 其餘的初始值為-1，表示沒有組合能夠組出這個數值
}
for (int i = 0; i <= amount; ++i) // 從最小的值開始往上算
{
int min = INT_MAX;
for (int coin : coins) // 計算每一種幣值
{
if (i - coin >= 0 && dp[i - coin] != -1) // 這邊是關鍵，dp[i - coin]就是表示i-coin那個數值最少能用多少硬幣組成，如果等於-1就表示組不出來，所以i也不會組出來
{
int tmp = dp[i - coin] + 1; // 多加一個硬幣，所以加1
if (tmp < min) // 比出最小的組成數量
{
min = tmp;
}
}
}
if (min != INT_MAX)
{
dp[i] = min; // 如果min不為INT_MAX，表示i是能被組出來的，記錄在dp[i]裡面
}
}
return dp[amount]; // 結束上面的計算後，dp[amount]就是用最少硬幣組成amount的答案
}
關鍵就是在那個dp，要從下往上記錄那些值
另外也可以用遞迴的方式來做，不過我個人是不太推薦啦
因為實際上兩種方式的過程是一樣的，都是由小的值往上算(廢話不然怎麼算...)
只是思考的方式不一樣，寫成code之後也長得不一樣了
遞迴的話看起來是從上往下推的，code大概是這樣：
vector<int> m_coins;
int minCoinAmount(int amount, vector<int>& memo)
{
if (amount == 0)
return 0;
else if (amount < 0)
return -1;
if (memo[amount] != 0)
return memo[amount];
int res = INT_MAX;
for (int coin : m_coins)
{
int minCoin = minCoinAmount(amount - coin, memo); // 差別就是這個，他會把amount-coin拿去往下算，得到結果後再傳回來
if (minCoin >= 0 && minCoin < res)
res = minCoin + 1;
}
memo[amount] = (res == INT_MAX) ? -1 : res;
return memo[amount];
}
int coinChange(vector<int>& coins, int amount) {
vector<int> memo(amount + 1, 0);
m_coins = coins;
return minCoinAmount(amount, memo);
}
其實大概看code也能發現兩個作法概念是一樣的，所以就看想怎麼做而已
這個技巧可以應用在很多地方，我覺得可以好好琢磨一下
比如說旅遊交通金錢的規劃(之後會有相關的題目)之類的
那麼這題就到這邊了~ 下題再見~
留言列表
