2025年USACOSilver模擬試卷（中等算法與問題解決）——動態(tài)規(guī)劃經(jīng)典題解一、編程題1.**最長公共子序列（LCS）**要求：給定兩個字符串A和B，找到它們的最長公共子序列。編寫一個函數(shù)，返回最長公共子序列的長度。輸入：```A="ABCDGH"B="AEDFHR"```輸出：```4```說明：最長的公共子序列為"ADH"，長度為4。2.**最長遞增子序列（LIS）**要求：給定一個無序數(shù)組nums，返回其最長遞增子序列的長度。輸入：```nums=[10,9,2,5,3,7,101,18]```輸出：```4```說明：最長遞增子序列為[2,3,7,101]，長度為4。二、算法題1.**背包問題**要求：給定一個物品列表，每個物品有一個價值和一個重量，以及一個背包的最大承重。編寫一個函數(shù)，返回背包能夠裝載的最大價值。輸入：```values=[60,100,120]weights=[10,20,30]capacity=50```輸出：```220```說明：選擇價值為100和120的物品，背包能夠裝載的最大價值為220。2.**編輯距離**要求：編寫一個函數(shù)，計算兩個字符串之間的編輯距離。編輯距離是指將一個字符串轉(zhuǎn)換成另一個字符串所需的最少編輯操作次數(shù)，其中編輯操作包括插入、刪除和替換。輸入：```str1="horse"str2="ros"```輸出：```3```說明：將"horse"轉(zhuǎn)換為"ros"需要進行3次編輯操作：將'h'替換為'r'，刪除'o'，將's'替換為'e'。三、綜合題1.**股票買賣**要求：給定一個股票價格數(shù)組，返回在每一天結(jié)束時，你可以通過買賣股票獲得的最大利潤。輸入：```prices=[7,1,5,3,6,4]```輸出：```7```說明：在第2天買入，第3天賣出，在第4天買入，第5天賣出，可以獲得最大利潤7。2.**打家劫舍**要求：給定一個非空整數(shù)數(shù)組，其中每個元素代表一個房子中存放的金幣數(shù)量，計算在不相鄰的房子中能夠盜取的最大金幣數(shù)量。輸入：```nums=[2,7,9,3,1]```輸出：```12```說明：選擇前兩個和最后一個房子，可以盜取最大金幣數(shù)量12。四、編程題1.**矩陣鏈乘法**要求：給定一個矩陣鏈，每個矩陣的維度已知，計算執(zhí)行矩陣鏈乘法所需的最少乘法次數(shù)。輸入：```p=[30,35,15,5,10,20,25]```輸出：```15125```說明：矩陣鏈乘法所需的最少乘法次數(shù)為15125。2.**最長不上升子序列**要求：給定一個整數(shù)數(shù)組，找到并返回其最長不上升子序列的長度。輸入：```nums=[10,9,2,5,3,7,101,18]```輸出：```4```說明：最長不上升子序列為[10,9,2,5]，長度為4。五、算法題1.**區(qū)間調(diào)度**要求：給定一組會議時間區(qū)間，每個區(qū)間以開始和結(jié)束時間表示，找出所有可以同時進行的會議。輸入：```intervals=[[0,30],[5,10],[15,20]]```輸出：```[[0,10],[15,20]]```說明：可以同時進行的會議為[0,10]和[15,20]。2.**最小路徑覆蓋**要求：給定一個無向圖，圖中每條邊都有一個權(quán)重，找到覆蓋所有頂點的最小權(quán)重的路徑。輸入：```edges=[[0,1,2],[1,2,3],[2,3,4],[3,4,5]]```輸出：```10```說明：覆蓋所有頂點的最小權(quán)重路徑的權(quán)重總和為10。六、綜合題1.**最小費用路徑**要求：給定一個帶權(quán)重的網(wǎng)格圖，每個格子都有一個權(quán)重，從左上角到右下角的最小費用路徑是多少？輸入：```grid=[[1,3,1],[1,5,1],[4,2,1]]```輸出：```7```說明：從左上角到右下角的最小費用路徑的總權(quán)重為7。2.**數(shù)字三角形**要求：給定一個數(shù)字三角形，從頂部到底部選擇路徑，使得路徑上的數(shù)字之和最大。編寫一個函數(shù)，返回這個最大和。輸入：```triangle=[[2],[3,4],[6,5,7],[4,1,8,3]]```輸出：```20```說明：從頂部到底部的最大數(shù)字之和路徑為2->3->7->3，最大和為20。本次試卷答案如下：一、編程題1.**最長公共子序列（LCS）**```pythondeflcs(X,Y):m=len(X)n=len(Y)L=[[0]*(n+1)foriinrange(m+1)]foriinrange(m+1):forjinrange(n+1):ifi==0orj==0:L[i][j]=0elifX[i-1]==Y[j-1]:L[i][j]=L[i-1][j-1]+1else:L[i][j]=max(L[i-1][j],L[i][j-1])returnL[m][n]A="ABCDGH"B="AEDFHR"print(lcs(A,B))```解析思路：使用動態(tài)規(guī)劃方法，創(chuàng)建一個二維數(shù)組L，其中L[i][j]表示X的前i個字符和Y的前j個字符的最長公共子序列的長度。通過比較X和Y的字符，更新L數(shù)組，最后返回L[m][n]，即整個字符串的最長公共子序列長度。2.**最長遞增子序列（LIS）**```pythondeflengthOfLIS(nums):ifnotnums:return0lis=[1]*len(nums)foriinrange(1,len(nums)):forjinrange(0,i):ifnums[i]>nums[j]:lis[i]=max(lis[i],lis[j]+1)returnmax(lis)nums=[10,9,2,5,3,7,101,18]print(lengthOfLIS(nums))```解析思路：使用動態(tài)規(guī)劃方法，初始化一個列表lis，其中每個元素表示以該元素結(jié)尾的最長遞增子序列的長度。通過遍歷數(shù)組，更新lis列表，最后返回lis列表中的最大值，即整個數(shù)組的最長遞增子序列長度。二、算法題1.**背包問題**```pythondefknapsack(values,weights,capacity):n=len(values)dp=[[0]*(capacity+1)for_inrange(n+1)]foriinrange(1,n+1):forwinrange(1,capacity+1):ifweights[i-1]<=w:dp[i][w]=max(dp[i-1][w],dp[i-1][w-weights[i-1]]+values[i-1])else:dp[i][w]=dp[i-1][w]returndp[n][capacity]values=[60,100,120]weights=[10,20,30]capacity=50print(knapsack(values,weights,capacity))```解析思路：使用動態(tài)規(guī)劃方法，創(chuàng)建一個二維數(shù)組dp，其中dp[i][w]表示前i個物品在容量為w的背包中能夠裝載的最大價值。通過比較當前物品的重量和背包容量，更新dp數(shù)組，最后返回dp[n][capacity]，即整個背包能夠裝載的最大價值。2.**編輯距離**```pythondefminDistance(str1,str2):m,n=len(str1),len(str2)dp=[[0]*(n+1)for_inrange(m+1)]foriinrange(m+1):forjinrange(n+1):ifi==0:dp[i][j]=jelifj==0:dp[i][j]=ielifstr1[i-1]==str2[j-1]:dp[i][j]=dp[i-1][j-1]else:dp[i][j]=1+min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])returndp[m][n]str1="horse"str2="ros"print(minDistance(str1,str2))```解析思路：使用動態(tài)規(guī)劃方法，創(chuàng)建一個二維數(shù)組dp，其中dp[i][j]表示將str1的前i個字符轉(zhuǎn)換為str2的前j個字符所需的最少編輯操作次數(shù)。通過比較str1和str2的字符，更新dp數(shù)組，最后返回dp[m][n]，即整個字符串的編輯距離。三、綜合題1.**股票買賣**```pythondefmaxProfit(prices):max_profit=0foriinrange(1,len(prices)):ifprices[i]>prices[i-1]:max_profit+=prices[i]-prices[i-1]returnmax_profitprices=[7,1,5,3,6,4]print(maxProfit(prices))```解析思路：通過遍歷價格數(shù)組，比較當前價格和前一天的價格，如果當前價格高于前一天的價格，則計算利潤并累加。最后返回累加的利潤，即最大利潤。2.**打家劫舍**```pythondefrob(nums):ifnotnums:return0iflen(nums)==1:returnnums[0]returnmax(nums[0],rob(nums[1:]))nums=[2,7,9,3,1]print(rob(nums))```解析思路：使用遞歸方法，如果數(shù)組為空，則返回0；如果數(shù)組只有一個元素，則返回該元素；否則，比較當前元素和去掉當前元素后的最大利潤，返回兩者中的較大值。四、編程題1.**矩陣鏈乘法**```pythondefmatrixChainOrder(p):n=len(p)-1m=[[0]*(n+1)for_inrange(n+1)]s=[[0]*(n+1)for_inrange(n+1)]forchain_lengthinrange(2,n+1):foriinrange(1,n-chain_length+2):j=i+chain_length-1m[i][j]=float('inf')forkinrange(i,j):cost=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]ifcost<m[i][j]:m[i][j]=costs[i][j]=k+1returnm[1][n]p=[30,35,15,5,10,20,25]print(matrixChainOrder(p))```解析思路：使用動態(tài)規(guī)劃方法，創(chuàng)建兩個二維數(shù)組m和s，其中m[i][j]表示從矩陣i到矩陣j的乘法順序的最小代價，s[i][j]表示分割矩陣的位置。通過遍歷所有可能的分割位置，更新m和s數(shù)組，最后返回m[1][n]，即整個矩陣鏈乘法順序的最小代價。2.**最長不上升子序列**```pythondeflengthOfLIS(nums):ifnotnums:return0lis=[1]*len(nums)foriinrange(1,len(nums)):forjinrange(0,i):ifnums[i]<=nums[j]:lis[i]=max(lis[i],lis[j]+1)returnmax(lis)nums=[10,9,2,5,3,7,101,18]print(lengthOfLIS(nums))```解析思路：使用動態(tài)規(guī)劃方法，初始化一個列表lis，其中每個元素表示以該元素結(jié)尾的最長不上升子序列的長度。通過遍歷數(shù)組，更新lis列表，最后返回lis列表中的最大值，即整個數(shù)組的最長不上升子序列長度。五、算法題1.**區(qū)間調(diào)度**```pythondeferaseOverlapIntervals(intervals):ifnotintervals:return0intervals.sort(key=lambdax:x[1])count=1prev_end=intervals[0][1]foriinrange(1,len(intervals)):ifintervals[i][0]>=prev_end:count+=1prev_end=intervals[i][1]returnlen(intervals)-countintervals=[[0,30],[5,10],[15,20]]print(eraseOverlapIntervals(intervals))```解析思路：首先對區(qū)間數(shù)組進行排序，然后遍歷排序后的數(shù)組，比較當前區(qū)間的開始時間和前一個區(qū)間的結(jié)束時間，如果當前區(qū)間的開始時間大于等于前一個區(qū)間的結(jié)束時間，則表示沒有重疊，增加計數(shù)器。最后返回區(qū)間數(shù)組的長度減去計數(shù)器的值，即沒有重疊的區(qū)間數(shù)量。2.**最小路徑覆蓋**```pythondefminimumPathCover(edges):graph={}foru,v,_inedges:ifunotingraph:graph[u]=[]ifvnotingraph:graph[v]=[]graph[u].append(v)graph[v].append(u)visited=set()defdfs(node):visited.add(node)forneighboringraph[node]:ifneighbornotinvisited:dfs(neighbor)visited.remove(node)nodes=set(graph.keys())uncovered_nodes=nodes-visiteddfs(next(iter(nodes)))returnlen(uncovered_nodes)edges=[[0,1,2],[1,2,3],[2,3,4],[3,4,5]]print(minimumPathCover(edges))```解析思路：首先構(gòu)建一個圖，然后使用深度優(yōu)先搜索（DFS）遍歷圖，記錄訪問過的節(jié)點。最后，計算未訪問的節(jié)點數(shù)量，即覆蓋所有頂點的最小權(quán)重路徑的權(quán)重總和。六、綜合題1.**最小費用路徑**```pythondefminPathSum(grid):m,n=len(grid),len(grid[0])dp=[[0]*nfor_inrange(m)]foriinrange(m):forjinrange(n):ifi==0andj==0:dp[i][j]=grid[i][j]elifi==0