Problem1

寻找能满足面值和的最小硬币数
考察点：BP(背包问题)
Description:
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:

Input: coins = [2], amount = 3
Output: -1
Note:
You may assume that you have an infinite number of each kind of coin.
(1）自己的解法（没有考虑到复杂情况，只是部分AC）：
想法既然是最小的硬币数，先将硬币按照面值进行排序，然后依次求商取余，这个方法有点自顶向下，没有考虑到总和最小其实就是组成和的部分的硬币数也要最小，没有反应出来这是一个背包问题(Knapsack problem)。

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        result=-1
        coin_sort=sorted(coins,reverse=True)
        if amount==0:
            result=0
        else:
            results=[]
            for i in range(len(coin_sort)):
                 rank=coin_sort[i]
                 if amount%rank==0:
                     result=amount//rank
                     break
                 else:
                    yushu=amount%rank
                    for j in range(i+1,len(coin_sort)):
                      if yushu%coin_sort[j]==0:
                         result=amount//rank+yushu//coin_sort[j]
                         results.append(result)
                      else:
                        
            if len(results)!=0:
                result = min(results)
        return result

（2)参考网上的解法，自己写的最终AC的程序：

    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        #创建保存部分硬币和的列表
        coin_split=[amount+1]*(amount+1)
        coin_split[0]=0
        for i in range(1,amount+1):
            for item in coins:
                if item<=i:
                    #每次循环判断取最小值
                    coin_split[i]=min(coin_split[i-item]+1,coin_split[i])
        if coin_split[amount]==amount+1:
            return -1
        else:
            return coin_split[amount]

Problem2

找股票的最佳收益
Description：
Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
（1)自己的想法：
找到数组中间的位置，找到中间位置之前的最小值，中间位置之后的最大值，两个数相减即为所求，这个思路有很多漏洞，只能部分AC
（2）参考网上别人的想法：
从前向后遍历的过程中，更新股票的最小面值以及收益，之前的想法是在循环的过程中不断的在剩余的数组中找最小值，这个方法的时间复杂度有点高O(n^2）

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) == 0:
            return 0
        
        minPrice = prices[0]
        maxProfit = 0
        for i in range(1, len(prices)):
            minPrice = min(prices[i], minPrice)
            maxProfit = max(prices[i] - minPrice, maxProfit)
            
        return maxProfit