遞歸與動態規劃試題及答案1.計算斐波那契數列第n項。-遞歸實現：```pythondeffibonacci_recursive(n):ifn<=1:returnnreturnfibonacci_recursive(n-1)+fibonacci_recursive(n-2)```答案分析：遞歸方式是根據斐波那契數列定義`F(n)=F(n-1)+F(n-2)`，有終止條件`n<=1`時返回`n`。但會有大量重復計算，時間復雜度為$O(2^n)$。-動態規劃實現：```pythondeffibonacci_dp(n):ifn<=1:returnndp=[0]*(n+1)dp[0]=0dp[1]=1foriinrange(2,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]```答案分析：動態規劃通過數組`dp`記錄子問題結果，避免重復計算，時間復雜度為$O(n)$，空間復雜度為$O(n)$。2.爬樓梯問題：假設你正在爬樓梯，需要n階你才能到達樓頂。每次你可以爬1或2個臺階。你有多少種不同的方法可以爬到樓頂呢？-遞歸實現：```pythondefclimb_stairs_recursive(n):ifn==1:return1ifn==2:return2returnclimb_stairs_recursive(n-1)+climb_stairs_recursive(n-2)```答案分析：遞歸思路源于到達第`n`階樓梯可從第`n-1`階走1步或第`n-2`階走2步到達，與斐波那契類似，有重復計算問題，時間復雜度$O(2^n)$。-動態規劃實現：```pythondefclimb_stairs_dp(n):ifn==1:return1ifn==2:return2dp=[0]*(n+1)dp[1]=1dp[2]=2foriinrange(3,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]```答案分析：動態規劃用數組`dp`記錄子問題結果，避免重復，時間復雜度$O(n)$，空間復雜度$O(n)$。3.最大子數組和：給定一個整數數組`nums`，找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。-遞歸實現（稍復雜且非最佳）：```pythondefmax_subarray_recursive(nums,start,end):ifstart==end:returnnums[start]mid=(start+end)//2left_max=max_subarray_recursive(nums,start,mid)right_max=max_subarray_recursive(nums,mid+1,end)cross_max=float('-inf')left_cross_sum=0foriinrange(mid,start-1,-1):left_cross_sum+=nums[i]cross_max=max(cross_max,left_cross_sum)right_cross_sum=0foriinrange(mid+1,end+1):right_cross_sum+=nums[i]cross_max+=right_cross_sumreturnmax(left_max,right_max,cross_max)```答案分析：遞歸采用分治法，將數組分為左右兩部分，分別求左、右和跨越中間的最大子數組和，再取最大值。時間復雜度$O(nlogn)$。-動態規劃實現：```pythondefmax_subarray_dp(nums):n=len(nums)dp=[0]*ndp[0]=nums[0]max_sum=dp[0]foriinrange(1,n):dp[i]=max(dp[i-1]+nums[i],nums[i])max_sum=max(max_sum,dp[i])returnmax_sum```答案分析：動態規劃用`dp[i]`表示以第`i`個元素結尾的最大子數組和，狀態轉移方程`dp[i]=max(dp[i-1]+nums[i],nums[i])`，時間復雜度$O(n)$，空間復雜度$O(n)$。4.硬幣找零問題：給定不同面額的硬幣`coins`和一個總金額`amount`，計算可以湊成總金額所需的最少的硬幣個數。如果沒有任何一種硬幣組合能組成總金額，返回-1。-遞歸實現：```pythonimportsysdefcoin_change_recursive(coins,amount):defhelper(remaining):ifremaining<0:return-1ifremaining==0:return0min_coins=sys.maxsizeforcoinincoins:result=helper(remaining-coin)ifresult>=0:min_coins=min(min_coins,result+1)returnmin_coinsifmin_coins!=sys.maxsizeelse-1returnhelper(amount)```答案分析：遞歸函數`helper`嘗試用每種硬幣去湊剩余金額，不斷遞歸。會有大量重復計算，時間復雜度指數級。-動態規劃實現：```pythondefcoin_change_dp(coins,amount):dp=[float('inf')]*(amount+1)dp[0]=0forcoinincoins:foriinrange(coin,amount+1):dp[i]=min(dp[i],dp[i-coin]+1)returndp[amount]ifdp[amount]!=float('inf')else-1```答案分析：動態規劃用`dp[i]`表示湊成金額`i`的最少硬幣數，狀態轉移方程`dp[i]=min(dp[i],dp[i-coin]+1)`，時間復雜度$O(amount*len(coins))$，空間復雜度$O(amount)$。5.計算排列數$A_{n}^k$：從`n`個不同元素中取出`k`個元素的所有排列的個數。-遞歸實現：```pythondefpermutation_recursive(n,k):ifk==0:return1returnn*permutation_recursive(n-1,k-1)```答案分析：遞歸基于排列數公式$A_{n}^k=n\timesA_{n-1}^{k-1}$，當`k==0`時為終止條件，時間復雜度$O(k)$。-動態規劃實現：```pythondefpermutation_dp(n,k):dp=[[0]*(k+1)for_inrange(n+1)]foriinrange(n+1):dp[i][0]=1foriinrange(1,n+1):forjinrange(1,min(i,k)+1):dp[i][j]=i*dp[i-1][j-1]returndp[n][k]```答案分析：動態規劃用二維數組`dp[i][j]`表示$A_{i}^j$，根據公式填充，時間復雜度$O(nk)$，空間復雜度$O(nk)$。6.計算組合數$C_{n}^k$：從`n`個不同元素中取出`k`個元素的所有組合的個數。-遞歸實現：```pythondefcombination_recursive(n,k):ifk==0ork==n:return1returncombination_recursive(n-1,k-1)+combination_recursive(n-1,k)```答案分析：遞歸基于組合數公式$C_{n}^k=C_{n-1}^{k-1}+C_{n-1}^k$，有重復計算，時間復雜度指數級。-動態規劃實現：```pythondefcombination_dp(n,k):dp=[[0]*(k+1)for_inrange(n+1)]foriinrange(n+1):forjinrange(min(i,k)+1):ifj==0orj==i:dp[i][j]=1else:dp[i][j]=dp[i-1][j-1]+dp[i-1][j]returndp[n][k]```答案分析：動態規劃用二維數組`dp[i][j]`表示$C_{i}^j$，根據公式填充，時間復雜度$O(nk)$，空間復雜度$O(nk)$。7.走迷宮問題（簡單，只能向右和向下走）：有一個`mxn`的迷宮，從左上角走到右下角有多少條不同的路徑。-遞歸實現：```pythondefunique_paths_recursive(m,n):ifm==1orn==1:return1returnunique_paths_recursive(m-1,n)+unique_paths_recursive(m,n-1)```答案分析：遞歸思路是到達`(m,n)`可從`(m-1,n)`向下或`(m,n-1)`向右到達，終止條件是在第一行或第一列，有重復計算，時間復雜度指數級。-動態規劃實現：```pythondefunique_paths_dp(m,n):dp=[[0]*nfor_inrange(m)]foriinrange(m):dp[i][0]=1forjinrange(n):dp[0][j]=1foriinrange(1,m):forjinrange(1,n):dp[i][j]=dp[i-1][j]+dp[i][j-1]returndp[m-1][n-1]```答案分析：動態規劃用二維數組`dp[i][j]`表示到達`(i,j)`的路徑數，根據遞歸關系填充，時間復雜度$O(mn)$，空間復雜度$O(mn)$。8.帶障礙物的走迷宮問題：在上述迷宮基礎上，某些格子有障礙物，不能通過。-遞歸實現：```pythondefunique_paths_with_obstacles_recursive(obstacleGrid):m=len(obstacleGrid)n=len(obstacleGrid[0])defhelper(i,j):ifi<0orj<0orobstacleGrid[i][j]==1:return0ifi==0andj==0:return1returnhelper(i-1,j)+helper(i,j-1)returnhelper(m-1,n-1)```答案分析：遞歸需判斷是否越界或遇到障礙物，有重復計算問題，時間復雜度指數級。-動態規劃實現：```pythondefunique_paths_with_obstacles_dp(obstacleGrid):m=len(obstacleGrid)n=len(obstacleGrid[0])dp=[[0]*nfor_inrange(m)]ifobstacleGrid[0][0]==0:dp[0][0]=1foriinrange(m):forjinrange(n):ifobstacleGrid[i][j]==1:continueifi-1>=0:dp[i][j]+=dp[i-1][j]ifj-1>=0:dp[i][j]+=dp[i][j-1]returndp[m-1][n-1]```答案分析：動態規劃在`dp`數組填充時跳過障礙物，利用`dp`數組記錄不同點的路徑數，時間復雜度$O(mn)$，空間復雜度$O(mn)$。9.子集和問題：給定一個正整數集合`nums`和一個目標和`target`，判斷是否存在一個子集，其元素之和等于`target`。-遞歸實現：```pythondefsubset_sum_recursive(nums,target,i):iftarget==0:returnTrueifi==len(nums):returnFalseinclude=subset_sum_recursive(nums,target-nums[i],i+1)exclude=subset_sum_recursive(nums,target,i+1)returnincludeorexclude```答案分析：遞歸有選或不選當前元素兩種情況，時間復雜度$O(2^n)$。-動態規劃實現：```pythondefsubset_sum_dp(nums,target):n=len(nums)dp=[[False]*(target+1)for_inrange(n+1)]foriinrange(n+1):dp[i][0]=Trueforiinrange(1,n+1):forjinrange(1,target+1):dp[i][j]=dp[i-1][j]ifj>=nums[i-1]:dp[i][j]=dp[i][j]ordp[i-1][j-nums[i-1]]returndp[n][target]```答案分析：動態規劃用二維數組`dp[i][j]`表示前`i`個元素能否組成和為`j`，時間復雜度$O(n*target)$，空間復雜度$O(n*target)$。10.最長遞增子序列（LIS）：給定一個無序的整數數組，找到其中最長遞增子序列的長度。-遞歸實現：```pythondeflis_recursive(nums,prev_index,current_index):ifcurrent_index==len(nums):return0taken=0ifprev_index==-1ornums[current_index]>nums[prev_index]:taken=1+lis_recursive(nums,current_index,current_index+1)not_taken=lis_recursive(nums,prev_index,current_index+1)returnmax(taken,not_taken)```答案分析：遞歸思路是選或不選當前元素來形成遞增子序列，有重復計算，時間復雜度指數級。-動態規劃實現：```pythondeflis_dp(nums):n=len(nums)dp=[1]*nforiinrange(1,n):forjinrange(i):ifnums[i]>nums[j]:dp[i]=max(dp[i],dp[j]+1)returnmax(dp)```答案分析：動態規劃用`dp[i]`表示以第`i`個元素結尾的最長遞增子序列長度，通過兩層循環更新，時間復雜度$O(n^2)$，空間復雜度$O(n)$。11.編輯距離問題：給定兩個字符串`word1`和`word2`，計算將`word1`轉換成`word2`所使用的最少操作次數。可以對一個字符串進行三種操作：插入一個字符、刪除一個字符、替換一個字符。-遞歸實現：```pythondefmin_distance_recursive(word1,word2,i,j):ifi==len(word1):returnlen(word2)-jifj==len(word2):returnlen(word1)-iifword1[i]==word2[j]:returnmin_distance_recursive(word1,word2,i+1,j+1)insert_op=min_distance_recursive(word1,word2,i,j+1)delete_op=min_distance_recursive(word1,word2,i+1,j)replace_op=min_distance_recursive(word1,word2,i+1,j+1)returnmin(insert_op,delete_op,replace_op)+1```答案分析：遞歸判斷字符是否相等，若不相等分別考慮插入、刪除、替換操作，有大量重復，時間復雜度指數級。-動態規劃實現：```pythondefmin_distance_dp(word1,word2):m=len(word1)n=len(word2)dp=[[0]*(n+1)for_inrange(m+1)]foriinrange(m+1):dp[i][0]=iforjinrange(n+1):dp[0][j]=jforiinrange(1,m+1):forjinrange(1,n+1):ifword1[i-1]==word2[j-1]:dp[i][j]=dp[i-1][j-1]else:dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1returndp[m][n]```答案分析：動態規劃用二維數組`dp[i][j]`表示`word1`前`i`個字符到`word2`前`j`個字符的編輯距離，狀態轉移基于字符是否相等，時間復雜度$O(mn)$，空間復雜度$O(mn)$。12.粉刷房子問題：有一排`n`個房子，每個房子可以被粉刷成紅色、藍色或綠色三種顏色中的一種。相鄰的房子不能粉刷成相同的顏色。每個房子粉刷成不同顏色的花費是不同的。計算粉刷完所有房子所需的最小花費。-遞歸實現：```pythondefmin_cost_recursive(costs,i,prev_color):ifi==len(costs):return0min_cost=float('inf')forcolorinrange(3):ifcolor!=prev_color:cost=costs[i][color]+min_cost_recursive(costs,i+1,color)min_cost=min(min_cost,cost)returnmin_cost```答案分析：遞歸遍歷每種顏色選擇，避免相鄰同色，有大量重復計算。-動態規劃實現：```pythondefmin_cost_dp(costs):ifnotcosts:return0n=len(costs)dp=[[0]*3for_inrange(n+1)]foriinrange(1,n+1):dp[i][0]=costs[i-1][0]+min(dp[i-1][1],dp[i-1][2])dp[i][1]=costs[i-1][1]+min(dp[i-1][0],dp[i-1][2])dp[i][2]=costs[i-1][2]+min(dp[i-1][0],dp[i-1][1])returnmin(dp[n])```答案分析：動態規劃用`dp[i][color]`表示粉刷前`i`個房子且第`i`個房子粉刷成`color`顏色的最小花費，狀態轉移考慮相鄰不同色，時間復雜度$O(3n)=O(n)$，空間復雜度$O(3n)=O(n)$。13.切割鋼條問題：給定一根長度為`n`的鋼條和一個價格表`prices`，`prices[i]`表示長度為`i+1`的鋼條的價格。求切割鋼條能獲得的最大收益。-遞歸實現：```pythondefcut_rod_recursive(prices,n):ifn==0:return0max_profit=0foriinrange(n):profit=prices[i]+cut_rod_recursive(prices,n-i-1)max_profit=max(max_profit,profit)returnmax_profit```答案分析：遞歸遍歷所有可能的切割點，有重復子問題。-動態規劃實現：```pythondefcut_rod_dp(prices,n):dp=[0]*(n+1)foriinrange(1,n+1):max_profit=0forjinrange(i):max_profit=max(max_profit,prices[j]+dp[i-j-1])dp[i]=max_profitreturndp[n]```答案分析：動態規劃用`dp[i]`表示長度為`i`的鋼條的最大收益，時間復雜度$O(n^2)$，空間復雜度$O(n)$。14.矩陣鏈乘法問題：給定`n`個矩陣構成的鏈$A_1,A_2,\cdots,A_n$，矩陣$A_i$的維度為$p_{i-1}\timesp_i$，求完全括號化方案使得矩陣鏈乘法的標量乘法次數最少。-遞歸實現：```pythondefmatrix_chain_recursive(p,i,j):ifi==j:return0min_cost=float('inf')forkinrange(i,j):cost=matrix_chain_recursive(p,i,k)+matrix_chain_recursive(p,k+1,j)+p[i-1]*p[k]*p[j]min_cost=min(min_cost,cost)returnmin_cost```答案分析：遞歸遍歷所有可能的分割點，會有重復計算，時間復雜度指數級。-動態規劃實現：```pythondefmatrix_chain_dp(p):n=len(p)-1dp=[[0]*(n+1)for_inrange(n+1)]forlinrange(2,n+1):foriinrange(1,n-l+2):j=i+l-1dp[i][j]=float('inf')forkinrange(i,j):cost=dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j]dp[i][j]=min(dp[i][j],cost)returndp[1][n]```答案分析：動態規劃用二維數組`dp[i][j]`表示矩陣鏈$A_i,A_{i+1},\cdots,A_j$的最少乘法次數，通過三層循環填充，時間復雜度$O(n^3)$，空間復雜度$O(n^2)$。15.最長公共子序列（LCS）：給定兩個字符串`text1`和`text2`，返回這兩個字符串的最長公共子序列的長度。-遞歸實現：```pythondeflcs_recursive(text1,text2,i,j):ifi==0orj==0:return0iftext1[i-1]==text2[j-1]:return1+lcs_recursive(text1,text2,i-1,j-1)returnmax(lcs_recursive(text1,text2,i-1,j),lcs_recursive(text1,text2,i,j-1))```答案分析：遞歸基于字符是否相等決定是否增加長度，有重復計算問題。-動態規劃實現：```pythondeflcs_dp(text1,text2):m=len(text1)n=len(text2)dp=[[0]*(n+1)for_inrange(m+1)]foriinrange(1,m+1):forjinrange(1,n+1):iftext1[i-1]==text2[j-1]:dp[i][j]=dp[i-1][j-1]+1else:dp[i][j]=max(dp[i-1][j],dp[i][j-1])returndp[m][n]```答案分析：動態規劃用二維數組`dp[i][j]`表示`text1`前`i`個字符和`text2`前`j`個字符的最長公共子序列長度，時間復雜度$O(mn)$，空間復雜度$O(mn)$。16.買賣股票的最佳時機：給定一個數組`prices`，它的第`i`個元素`prices[i]`表示一支給定股票第`i`天的價格。你只能選擇某一天買入這只股票，并選擇在未來的某一個不同的日子賣出該股票。設計一個算法來計算你所能