from typing import List


def coinChange(coins: List[int], amount: int) -> int:
 max_value = 1 << 32
 dp = [max_value for i in range(amount + 1)]
 for i in range(amount + 1):
 if i == 0:
 dp[0] = 0
 else:
 for c in coins:
 if i - c >= 0 and dp[i - c] != max_value:
 dp[i] = min(dp[i - c] + 1, dp[i])

 return -1 if dp[amount] == max_value else dp[amount]


# dp[i]表示前家能抢到的钱的最大数目
def rob(nums: List[int]) -> int:
 dp = [0 for _ in range(len(nums) + 1)]
 if len(nums) == 1:
 dp[0] = nums[0]
 return dp[0]
 elif len(nums) == 2:
 dp[1] = max(nums)
 return dp[1]
 else:
 dp[0] = nums[0]
 dp[1] = max(nums[0], nums[1])
 for i in range(2, len(nums)):
 dp[i] = (max(dp[i - 2] + nums[i], dp[i - 1]))
 return dp[len(nums) - 1]


def maxProfit(prices):
 length = len(prices)
 if length <= 1:
 return 0
 else:
 cache = 0
 int_value = prices[0]
 for index in range(length):
 if prices[index] < int_value:
 int_value = prices[index]
 result = max(cache, prices[index] - int_value)
 cache = result
 return result