Simple series
1. Shares
Suppose you have an array in which\ i i The first element is the stock in the second\ i i Day price. You have a chance to buy and sell. You can't sell a stock until you buy it. Please design an algorithm to calculate the maximum benefit. https://www.nowcoder.com/practice/64b4262d4e6d4f6181cd45446a5821ec?tpId=188&&tqId=38556&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking Input:[1,4,2] Return value: 3 Input:[2,4,1] Return value: 2
The known condition is one-dimensional, and the solution can be expressed by a variable
#
#
# @param prices int integer one-dimensional array
# @return int integer
#
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 win2. Minimum sum of road stiffness of matrix
Given a n * m Matrix of a，Starting from the upper left corner, you can only go right or down at a time, and finally reach the lower right corner. The sum of all the numbers on the path is the path sum, and the smallest path sum of all the paths is output. 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 Input:[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]] Return value: 12
The known condition is two-dimensional, and what is sought is expressed in two dimensions
DP [i] [J] + = min (from the top, from the right)
#
#
# @param matrix int integer two-dimensional array the matrix
# @return int integer
#
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 ):
'''This is a recursive method. Looking back from the requested position will timeout'''
#return self.digui(matrix, len(matrix)-1,len(matrix[0])-1)
'''This is dynamic programming, which finds the target position from the initial position'''
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 Minimum amount of money to change
Given array arr，arr All values in are positive integers and do not repeat. Each value represents a currency with a face value. Any currency with a face value can be given aim，Represents the amount of money you want to find aim Minimum number of currencies. If there is no solution, please return-1. Time complexity O(n \times aim)O(n×aim)，Spatial complexity On. Input:[5,2,3],20 Return value: 4
If you have three convertible denominations, use the sum of these denominations to represent 20, and the amount of money is the least. If you use the numerical expression method, there will be an unsolvable solution, which is suitable for dynamic programming.
20 = 15 + 5, then 15 = 10 + 5, 10 = 5 + 5, 5 can be directly represented by face value.
Suppose from 0 to 20 yuan, the money you can get by pushing forward from the known face value:
0 yuan can't be expressed in any case. 0 yuan was used
1 yuan is the face value of 5, 2 and 3, which can not be obtained in any case. Suppose x, X means that it is larger than the number of sheets with the most money
You can get 2 yuan in face value. I used 1 piece of money
Three yuan can only be obtained from the face value of three. I used one piece of money
4 yuan can only be obtained with 2 * face value 2. Two pieces of money were used. The number of pieces with face value 1 + face value 3 was x, and finally two pieces were used
Five yuan can be obtained by using face value 3 + face value 2, using two pieces of money, or using face value 5 and using one piece of money. According to the requirements, at least one piece of money shall be used. With other face values, the number of pieces of money is not the least. min(dp[5],dp[5-5]+1)=1 piece, min(dp[5],dp[5-2]+1)=min(1,2) = 1 piece, min(dp[5],dp[5-3]+1)=min(1,2) = 1 piece
dp[5-5]+1 means 5 yuan, and face value 5 indicates the number of subsequent pieces of money. Since face value 5 is available, it directly means 5 yuan, and 1 piece of money is used
For 6 yuan, you can use the money marked in red to have the face value of the least amount of money. You can use the face value marked in red to represent 6 yuan
=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) = the number of money sheets of 3,4 yuan has been calculated = 2
, min (DP [6], DP [6-3] + 1) = min (3, DP [3] + 1) = the number of money sheets of 2,3 yuan has been calculated = 1
Final = 2
And so on to 20.
DP [aim] = min (not represented by a certain value, but represented by a certain value) = min(dp[i],dp[i-j]+1),j is the value in arr, only if I is not J hours, I yuan can be expressed in the face value of arr.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
#
# Minimum currency
# @param arr int integer one dimensional array the array
# @param aim int integer the target
# @return int integer
#
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]