[数据结构与算法]动态规划(牛客网）

简单系列

1.股票

假设你有一个数组，其中第\ i i 个元素是股票在第\ i i 天的价格。
你有一次买入和卖出的机会。（只有买入了股票以后才能卖出）。请你设计一个算法来计算可以获得的最大收益。
https://www.nowcoder.com/practice/64b4262d4e6d4f6181cd45446a5821ec?tpId=188&&tqId=38556&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking

输入：[1,4,2]
返回值：3

输入：[2,4,1]
返回值：2

?已知条件是一维的，所求可以用一个变量表示

#
# 
# @param prices int整型一维数组 
# @return int整型
#
class Solution:
    def maxProfit(self , prices ):
        # write code here
        soldout = prices[0]
        buyin = prices[0]
        win = soldout - buyin
        for i in range(1,len(prices)):
          
          if prices[i]-buyin<=0:
            buyin = prices[i]
          if win<prices[i]-buyin:
            soldout=prices[i]
            win = soldout- buyin
        print(win)
        return win

2.矩阵的最小路劲和

给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

https://www.nowcoder.com/practice/7d21b6be4c6b429bb92d219341c4f8bb?tpId=188&&tqId=38601&rp=1&ru=/ta/job-code-high-week&qru=/ta/job-code-high-week/question-ranking

输入：[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]
返回值：12

已知条件是二维的，所求是用二维来表达

dp[i][j] += min(从上边先来,从右边过来）

#
# 
# @param matrix int整型二维数组 the matrix
# @return int整型
#
class Solution:
    def digui(self,matrix,i,j):
      if i==0 and j==0:
        return matrix[0][0]
      if i==0 and j!=0:
        return matrix[i][j]+matrix[0][j-1]
      if i!=0 and j==0:
        return matrix[i][j]+matrix[i-1][0]
      else:
        a = self.digui(matrix,i-1,j)
        b = self.digui(matrix, i, j-1)
        return matrix[i][j]+min(a, b)
      
    def minPathSum(self , matrix ):
       '''这是递归方法，从所求位置往回找，会超时'''
      #return self.digui(matrix, len(matrix)-1,len(matrix[0])-1)
        '''这是动态规划，从初始位置找到目标位置'''
      row,col = len(matrix[0]),len(matrix)
      #dp = matrix
      #dp[0][0] = matrix[0][0]
      for i in range(1,row):
        matrix[0][i] = matrix[0][i-1] + matrix[0][i]
      for j in range(1,col):
        matrix[j][0] = matrix[j-1][0] + matrix[j][0]
      for i in range(1,col):
        for j in range(1,row):
          matrix[i][j] = min(matrix[i-1][j],matrix[i][j-1]) + matrix[i][j]
      return matrix[i][j]
        # write code here
      

3.NC126?换钱的最少货币数

给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。
如果无解，请返回-1.

时间复杂度O(n \times aim)O(n×aim)，空间复杂度On。

输入：[5,2,3],20
返回值：4

对于拥有3种可以兑换的面值的话，用这些面值的和来表示20，且钱数最少。用数值表达的方法，会有解不出的解，用动态规划合适。

20=15+5 ，那么 15 = 10+5， 10 =5+5，5 可以直接被面值表示。

假设从0块到20块钱，从已知的面值往前推能够得到的钱：

0块钱是无论如何也无法表示的，用了0张钱

1块钱是5,2,3这些面值无论如何都得不到的，假设为x，x来表示比用最多的钱的张数还大

2块钱可以用面值2得到，用了1张钱

3块钱只能由面值3得到，用了1张钱

4块钱只能用2*面值2 得到，用了2张钱，用面值1+面值3的张数为x，最终用了2张

5块钱能用面值3+面值2得到，用了2张钱，或者用面值5得到，用1张钱，按照要求，最少用1张钱,用其他的面值，其钱的张数不是最少的。得到 min(dp[5],dp[5-5]+1)=1张,min(dp[5],dp[5-2]+1)=min(1,2）=1张,min(dp[5],dp[5-3]+1)=min(1,2）=1张

dp[5-5]+1 表示5块钱用面值5表示了之后的钱的张数，由于面值5是有的，直接表示5块钱，用了1张钱

6块钱，可以用标红的钱是能够拥有最少钱数的面值了，可以用标红的面值来表示6

=min(dp[6],dp[6-5]+1)=min(dp[6],dp[1]+1)=x,

min(dp[6],dp[6-2]+1)=min(x,dp[4]]+1) =?min(x,2+1) = 3,4块钱的用钱张数已经被求出来了=2

,min(dp[6],dp[6-3]+1)=min(3,dp[3]+1) = 2，3块钱的用钱张数已经被求出来了=1

最终 = 2

以此类推到20的时候。

dp[aim] = min(没用某个数值表示，用了某个数值来表示）=min(dp[i],dp[i-j]+1),j 是arr当中的值，只有当 i 不比? j 小时，i块钱 才能用arr当中的面值来表示。

#
# 最少货币数
# @param arr int整型一维数组 the array
# @param aim int整型 the target
# @return int整型
#
class Solution:
    def minMoney(self , arr , aim ):
        # write code here
        dp = [0]
        for i in range(aim):
          dp.append(aim)
        for i in range(1,aim+1):
          for j in arr:
            if i>=j:
              dp[i] = min(dp[i],dp[i-j]+1)
        if dp[aim]==aim:
          return -1
        else:
          return dp[aim]