刷题笔记—leetcode.302.coin-change

2020年03月09日 243点热度 0人点赞 0条评论

题目

302 | 中等
https://leetcode-cn.com/problems/coin-change/

题解

核心思想:动态规划
解析:
问题用数学的语言可以描述为

$$
\argmin_{\sum{x_i}}{\sum{x_i c_i} = S}
$$
$x_i$ 是硬币的数目,而 $c_i$ 是面额, $S$ 是目标总金额。

设 F(S) 为组合为目标总金额的硬币数目;则有递推公式为
$$
F(S) = F(S - c_i) + 1
$$

根据这个递推关系,问题被拆解为求$ F(S - c_i) + 1$的最小值。
初值条件为 F(0) = 0;

以此可以写出一个递归求解的方案;也可以不使用递归,从头开始建立查找表,直到目标值被确定。

  1. 递归解法 (自上而下搜索,再回溯)

// recursive solution class Solution { public: int coinChange(vector<int>& coins, int amount) { vector<int> lut(amount+1, 0); max_val = amount+1; return coinChange(coins, amount, lut); } private: int max_val; int coinChange(vector<int>& coins,int amount, vector<int> &lut){ if(amount < 0) return -1; if(amount == 0) return 0; if(lut[amount] != 0 ) return lut[amount]; int min_cost = max_val; for(auto coin : coins ){ int res = coinChange(coins, amount - coin, lut); if(res != -1){ min_cost = min(min_cost, res + 1); } } lut[amount] = (min_cost==max_val)? -1: min_cost; return lut[amount]; } };
  1. 非递归解法(从底部向上搜索)
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int max = amount+1;
        vector<int> dp(amount+1, max);
        dp[0] = 0;
        for(int i = 1; i < amount+1; i++){
           for(auto coin : coins){
            if(i >= coin)
              dp[i] = min( dp[i], dp[i - coin] + 1);
           }
        }

        return (dp[amount] == max)? -1: dp[amount];

    }
};

第2种方法更加容易理解,两种方法的时间复杂度是 O(S*n); 空间复杂度为O(s).

动态规划问题的基本特征

  1. 求一个问题的最优解
  2. 大问题可以划分为几个子问题
  3. 子问题之间有交叠的更小子问题
  4. 从上往下分析问题,从下往上求解问题
    —— 可以考虑使用动态规划^[《剑指offer 2.2.4 动态规划与贪婪算法》]

注:对于问题4, 个人观点是通常动态规划可以递归求解(从上往下回溯);但是我们不喜欢递归。动态规划好处是存储了交叠的更小子问题的解,在求解更上一层的信息的时候,可以复用之前缓存的信息。

Charles

Stay hungry, stay foolish.

文章评论