动态规划(牛客网）

admin 管理员组

文章数量: 1086019

目录

1.股票

2.矩阵的最小路径和

3.NC126 换钱的最少货币数

4.WC83 连续子数组的最大和

5.WC86 跳台阶扩展问题

6.WC104 矩形覆盖

简单系列

1.股票

假设你有一个数组，其中第\ i i 个元素是股票在第\ i i 天的价格。
你有一次买入和卖出的机会。（只有买入了股票以后才能卖出）。
请你设计一个算法来计算可以获得的最大收益。
https://www.nowcoder/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/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]

便利蜂的算法题的第一道是这个。

4.WC83 连续子数组的最大和

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。
求所有子数组的和的最大值。要求时间复杂度为 O(n).

输入：[1,-2,3,10,-4,7,2,-5]
返回值：18

https://www.nowcoder/practice/459bd355da1549fa8a49e350bf3df484?tpId=202&&tqId=38792&rp=1&ru=/activity/oj&qru=/ta/code-written-high/question-ranking

已知条件是一维，最终的结果可以用一个变量表示，

t= max(加上之前的累和，不加) = max(array[i]+t,array[i])

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
      maxre = array[0]
      t = array[0]
      for i in range(1,len(array)):
        t = max(t+array[i],array[i])
        maxre = max(maxre,t)
            
        
      print(maxre)
      return maxre
        # write code here

5.WC86 跳台阶扩展问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。
求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。

输入：3
返回值： 4

https://www.nowcoder/practice/22243d016f6b47f2a6928b4313c85387?tpId=202&&tqId=38795&rp=1&ru=/activity/oj&qru=/ta/code-written-high/question-ranking

题解数学知识

n级台阶有f(n)种方法

考虑最后一次跳了1个台阶，那么前面 n-1 个台阶有 f(n-1)种方法

考虑最后一次跳了2个台阶，那么前面 n-2 个台阶有 f(n-2)种方法

考虑最后一次跳了3个台阶，那么前面 n-3 个台阶有 f(n-3)种方法

……

直到

一次跳了n 个台阶

通过枚举各种情况后：

f(n) = f(n-1) +  f(n-2)+ f(n-3) +……+ f(1)

同理： f(n-1) =  f(n-2)+ f(n-3) +……+ f(1)

两个式子相减 ： f(n) =2* f(n-1) =2*(2*f(n-2)))=2*(2*(2*f(n-2))))=……=2^(n-1)

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
      dp= [0]
      if number>0:
        re = 2**(number-1)
      else:re=0
      return re
        # write code here

6.WC104 矩形覆盖

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。
请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，
从同一个方向看总共有多少种不同的方法？

比如n=3时，2*3的矩形块有3种不同的覆盖方法(从同一个方向看)：

输入：3
输出：3

https://www.nowcoder/practice/72a5a919508a4251859fb2cfb987a0e6?tpId=202&&tqId=38813&rp=1&ru=/activity/oj&qru=/ta/code-written-high/question-ranking

 找规律

number 0 -> 个数 0

number 1 -> 个数 1

number 2 -> 个数 2

number 3 -> 个数 3

number 4 -> 个数 5

number 5 -> 个数 8

number 6 -> 个数 13

f(n)=f(n-1)+f(n-2)

# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
      even = 2
      odd = 1
      dp=[]
      dp.append(0)
      dp.append(1)
      dp.append(2)
      for i in range(3,number+1):
        dp.append(dp[i-1]+dp[i-2])
      return dp[number]

本文标签： 动态 牛客网