509.斐波那契数 | 322.零钱兑换

509.斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。

示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

思路：动态规划

先写状态转移方程，然后写出暴力解法，再添加备忘录，完成剪枝

class Solution {
public:
    int fib(int n) {
        int cur=0;
        int next=1;
        if(n==0||n==1)
        return n;
        int res=0;
        for(int i=2;i<=n;i++)
        {
            res=cur+next;
            cur=next;
            next=res;
        }
        return res;
    }
};

322.零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
示例 2：

输入：coins = [2], amount = 3
输出：-1
示例 3：

输入：coins = [1], amount = 0
输出：0

思路：动态规划

先写状态转移方程，然后写出暴力解法，再添加备忘录，完成剪枝

用dp函数自顶向下做 

class Solution {
public:
    //count=1+min(coinChange([1,2,5],11-1),coinChange([1,2,5],11-2),coinChange([1,2,5],11-5))
    //helper()函数定义：输入一个amount，返回可以凑成它的最少硬币个数
    int coinChange(vector<int>& coins, int amount) {
        vector<int> memo(amount+1,INT_MIN);//备忘录
        int ans=helper(coins,amount,memo);
        return ans;
    }
    int helper(vector<int>& coins,int amount,vector<int>& memo)
    {
        if(amount==0)
            return 0;
        if(amount<0)//amount小于0，说明凑不出来
            return -1;
        if(memo[amount]!=INT_MIN)
            return memo[amount];
        int res=INT_MAX;
        for(int coin:coins)
        {
            //计算子问题的结果
            int count=helper(coins,amount-coin,memo);
            if(count==-1)//说明子问题凑不出来，就跳过
            continue;
            res=min(res,count);
        }
        if(res==INT_MAX)
            memo[amount]=-1;
        else
            memo[amount]=res+1;
        return memo[amount];
    }
};

用dp数组自底向上做：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        //设置为amount+1是因为，全用1元硬币凑amount需要amount枚，所以amount+1比最大枚数还要大
        //但不能设置为INT_MAX，不然INT_MAX和INT_MAX+1，是无法比较出最小值的
        vector<int> dp(amount+1,amount+1);
        dp[0]=0;
        for(int i=1;i<=amount;i++)
        {
            for(int coin:coins)
            {
                if(i-coin<0)
                {
                    continue;
                }
                dp[i]=min(dp[i],dp[i-coin]+1);
            }
        }
        return dp[amount]==amount+1?-1:dp[amount];
    }
};