遞歸與動(dòng)態(tài)規(guī)劃試題及答案

遞歸與動(dòng)態(tài)規(guī)劃試題及答案1.計(jì)算斐波那契數(shù)列第n項(xiàng)。-遞歸實(shí)現(xiàn)：```pythondeffibonacci_recursive(n):ifn<=1:returnnreturnfibonacci_recursive(n-1)+fibonacci_recursive(n-2)```答案分析：遞歸方式是根據(jù)斐波那契數(shù)列定義`F(n)=F(n-1)+F(n-2)`，有終止條件`n<=1`時(shí)返回`n`。但會(huì)有大量重復(fù)計(jì)算，時(shí)間復(fù)雜度為$O(2^n)$。-動(dòng)態(tài)規(guī)劃實(shí)現(xià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]```答案分析：動(dòng)態(tài)規(guī)劃通過數(shù)組`dp`記錄子問題結(jié)果，避免重復(fù)計(jì)算，時(shí)間復(fù)雜度為$O(n)$，空間復(fù)雜度為$O(n)$。2.爬樓梯問題：假設(shè)你正在爬樓梯，需要n階你才能到達(dá)樓頂。每次你可以爬1或2個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？-遞歸實(shí)現(xiàn)：```pythondefclimb_stairs_recursive(n):ifn==1:return1ifn==2:return2returnclimb_stairs_recursive(n-1)+climb_stairs_recursive(n-2)```答案分析：遞歸思路源于到達(dá)第`n`階樓梯可從第`n-1`階走1步或第`n-2`階走2步到達(dá)，與斐波那契類似，有重復(fù)計(jì)算問題，時(shí)間復(fù)雜度$O(2^n)$。-動(dòng)態(tài)規(guī)劃實(shí)現(xià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]```答案分析：動(dòng)態(tài)規(guī)劃用數(shù)組`dp`記錄子問題結(jié)果，避免重復(fù)，時(shí)間復(fù)雜度$O(n)$，空間復(fù)雜度$O(n)$。3.最大子數(shù)組和：給定一個(gè)整數(shù)數(shù)組`nums`，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。-遞歸實(shí)現(xiàn)（稍復(fù)雜且非最佳）：```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)```答案分析：遞歸采用分治法，將數(shù)組分為左右兩部分，分別求左、右和跨越中間的最大子數(shù)組和，再取最大值。時(shí)間復(fù)雜度$O(nlogn)$。-動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)：```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```答案分析：動(dòng)態(tài)規(guī)劃用`dp[i]`表示以第`i`個(gè)元素結(jié)尾的最大子數(shù)組和，狀態(tài)轉(zhuǎn)移方程`dp[i]=max(dp[i-1]+nums[i],nums[i])`，時(shí)間復(fù)雜度$O(n)$，空間復(fù)雜度$O(n)$。4.硬幣找零問題：給定不同面額的硬幣`coins`和一個(gè)總金額`amount`，計(jì)算可以湊成總金額所需的最少的硬幣個(gè)數(shù)。如果沒有任何一種硬幣組合能組成總金額，返回-1。-遞歸實(shí)現(xiàn)：```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)```答案分析：遞歸函數(shù)`helper`嘗試用每種硬幣去湊剩余金額，不斷遞歸。會(huì)有大量重復(fù)計(jì)算，時(shí)間復(fù)雜度指數(shù)級(jí)。-動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)：```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```答案分析：動(dòng)態(tài)規(guī)劃用`dp[i]`表示湊成金額`i`的最少硬幣數(shù)，狀態(tài)轉(zhuǎn)移方程`dp[i]=min(dp[i],dp[i-coin]+1)`，時(shí)間復(fù)雜度$O(amount*len(coins))$，空間復(fù)雜度$O(amount)$。5.計(jì)算排列數(shù)$A_{n}^k$：從`n`個(gè)不同元素中取出`k`個(gè)元素的所有排列的個(gè)數(shù)。-遞歸實(shí)現(xiàn)：```pythondefpermutation_recursive(n,k):ifk==0:return1returnn*permutation_recursive(n-1,k-1)```答案分析：遞歸基于排列數(shù)公式$A_{n}^k=n\timesA_{n-1}^{k-1}$，當(dāng)`k==0`時(shí)為終止條件，時(shí)間復(fù)雜度$O(k)$。-動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)：```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]```答案分析：動(dòng)態(tài)規(guī)劃用二維數(shù)組`dp[i][j]`表示$A_{i}^j$，根據(jù)公式填充，時(shí)間復(fù)雜度$O(nk)$，空間復(fù)雜度$O(nk)$。6.計(jì)算組合數(shù)$C_{n}^k$：從`n`個(gè)不同元素中取出`k`個(gè)元素的所有組合的個(gè)數(shù)。-遞歸實(shí)現(xiàn)：```pythondefcombination_recursive(n,k):ifk==0ork==n:return1returncombination_recursive(n-1,k-1)+combination_recursive(n-1,k)```答案分析：遞歸基于組合數(shù)公式$C_{n}^k=C_{n-1}^{k-1}+C_{n-1}^k$，有重復(fù)計(jì)算，時(shí)間復(fù)雜度指數(shù)級(jí)。-動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)：```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]```答案分析：動(dòng)態(tài)規(guī)劃用二維數(shù)組`dp[i][j]`表示$C_{i}^j$，根據(jù)公式填充，時(shí)間復(fù)雜度$O(nk)$，空間復(fù)雜度$O(nk)$。7.走迷宮問題（簡單，只能向右和向下走）：有一個(gè)`mxn`的迷宮，從左上角走到右下角有多少條不同的路徑。-遞歸實(shí)現(xiàn)：```pythondefunique_paths_recursive(m,n):ifm==1orn==1:return1returnunique_paths_recursive(m-1,n)+unique_paths_recursive(m,n-1)```答案分析：遞歸思路是到達(dá)`(m,n)`可從`(m-1,n)`向下或`(m,n-1)`向右到達(dá)，終止條件是在第一行或第一列，有重復(fù)計(jì)算，時(shí)間復(fù)雜度指數(shù)級(jí)。-動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)：```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]```答案分析：動(dòng)態(tài)規(guī)劃用二維數(shù)組`dp[i][j]`表示到達(dá)`(i,j)`的路徑數(shù)，根據(jù)遞歸關(guān)系填充，時(shí)間復(fù)雜度$O(mn)$，空間復(fù)雜度$O(mn)$。8.帶障礙物的走迷宮問題：在上述迷宮基礎(chǔ)上，某些格子有障礙物，不能通過。-遞歸實(shí)現(xiàn)：```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)```答案分析：遞歸需判斷是否越界或遇到障礙物，有重復(fù)計(jì)算問題，時(shí)間復(fù)雜度指數(shù)級(jí)。-動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)：```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]```答案分析：動(dòng)態(tài)規(guī)劃在`dp`數(shù)組填充時(shí)跳過障礙物，利用`dp`數(shù)組記錄不同點(diǎn)的路徑數(shù)，時(shí)間復(fù)雜度$O(mn)$，空間復(fù)雜度$O(mn)$。9.子集和問題：給定一個(gè)正整數(shù)集合`nums`和一個(gè)目標(biāo)和`target`，判斷是否存在一個(gè)子集，其元素之和等于`target`。-遞歸實(shí)現(xiàn)：```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```答案分析：遞歸有選或不選當(dāng)前元素兩種情況，時(shí)間復(fù)雜度$O(2^n)$。-動(dòng)態(tài)規(guī)劃實(shí)現(xià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]```答案分析：動(dòng)態(tài)規(guī)劃用二維數(shù)組`dp[i][j]`表示前`i`個(gè)元素能否組成和為`j`，時(shí)間復(fù)雜度$O(n*target)$，空間復(fù)雜度$O(n*target)$。10.最長遞增子序列（LIS）：給定一個(gè)無序的整數(shù)數(shù)組，找到其中最長遞增子序列的長度。-遞歸實(shí)現(xiàn)：```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)```答案分析：遞歸思路是選或不選當(dāng)前元素來形成遞增子序列，有重復(fù)計(jì)算，時(shí)間復(fù)雜度指數(shù)級(jí)。-動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)：```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)```答案分析：動(dòng)態(tài)規(guī)劃用`dp[i]`表示以第`i`個(gè)元素結(jié)尾的最長遞增子序列長度，通過兩層循環(huán)更新，時(shí)間復(fù)雜度$O(n^2)$，空間復(fù)雜度$O(n)$。11.編輯距離問題：給定兩個(gè)字符串`word1`和`word2`，計(jì)算將`word1`轉(zhuǎn)換成`word2`所使用的最少操作次數(shù)?？梢詫?duì)一個(gè)字符串進(jìn)行三種操作：插入一個(gè)字符、刪除一個(gè)字符、替換一個(gè)字符。-遞歸實(shí)現(xiàn)：```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```答案分析：遞歸判斷字符是否相等，若不相等分別考慮插入、刪除、替換操作，有大量重復(fù)，時(shí)間復(fù)雜度指數(shù)級(jí)。-動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)：```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]```答案分析：動(dòng)態(tài)規(guī)劃用二維數(shù)組`dp[i][j]`表示`word1`前`i`個(gè)字符到`word2`前`j`個(gè)字符的編輯距離，狀態(tài)轉(zhuǎn)移基于字符是否相等，時(shí)間復(fù)雜度$O(mn)$，空間復(fù)雜度$O(mn)$。12.粉刷房子問題：有一排`n`個(gè)房子，每個(gè)房子可以被粉刷成紅色、藍(lán)色或綠色三種顏色中的一種。相鄰的房子不能粉刷成相同的顏色。每個(gè)房子粉刷成不同顏色的花費(fèi)是不同的。計(jì)算粉刷完所有房子所需的最小花費(fèi)。-遞歸實(shí)現(xià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```答案分析：遞歸遍歷每種顏色選擇，避免相鄰?fù)?，有大量重?fù)計(jì)算。-動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)：```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])```答案分析：動(dòng)態(tài)規(guī)劃用`dp[i][color]`表示粉刷前`i`個(gè)房子且第`i`個(gè)房子粉刷成`color`顏色的最小花費(fèi)，狀態(tài)轉(zhuǎn)移考慮相鄰不同色，時(shí)間復(fù)雜度$O(3n)=O(n)$，空間復(fù)雜度$O(3n)=O(n)$。13.切割鋼條問題：給定一根長度為`n`的鋼條和一個(gè)價(jià)格表`prices`，`prices[i]`表示長度為`i+1`的鋼條的價(jià)格。求切割鋼條能獲得的最大收益。-遞歸實(shí)現(xiàn)：```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```答案分析：遞歸遍歷所有可能的切割點(diǎn)，有重復(fù)子問題。-動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)：```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]```答案分析：動(dòng)態(tài)規(guī)劃用`dp[i]`表示長度為`i`的鋼條的最大收益，時(shí)間復(fù)雜度$O(n^2)$，空間復(fù)雜度$O(n)$。14.矩陣鏈乘法問題：給定`n`個(gè)矩陣構(gòu)成的鏈$A_1,A_2,\cdots,A_n$，矩陣$A_i$的維度為$p_{i-1}\timesp_i$，求完全括號(hào)化方案使得矩陣鏈乘法的標(biāo)量乘法次數(shù)最少。-遞歸實(shí)現(xiàn)：```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```答案分析：遞歸遍歷所有可能的分割點(diǎn)，會(huì)有重復(fù)計(jì)算，時(shí)間復(fù)雜度指數(shù)級(jí)。-動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)：```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]```答案分析：動(dòng)態(tài)規(guī)劃用二維數(shù)組`dp[i][j]`表示矩陣鏈$A_i,A_{i+1},\cdots,A_j$的最少乘法次數(shù)，通過三層循環(huán)填充，時(shí)間復(fù)雜度$O(n^3)$，空間復(fù)雜度$O(n^2)$。15.最長公共子序列（LCS）：給定兩個(gè)字符串`text1`和`text2`，返回這兩個(gè)字符串的最長公共子序列的長度。-遞歸實(shí)現(xiàn)：```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))```答案分析：遞歸基于字符是否相等決定是否增加長度，有重復(fù)計(jì)算問題。-動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)：```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]```答案分析：動(dòng)態(tài)規(guī)劃用二維數(shù)組`dp[i][j]`表示`text1`前`i`個(gè)字符和`text2`前`j`個(gè)字符的最長公共子序列長度，時(shí)間復(fù)雜度$O(mn)$，空間復(fù)雜度$O(mn)$。16.買賣股票的最佳時(shí)機(jī)：給定一個(gè)數(shù)組`prices`，它的第`i`個(gè)元素`prices[i]`表示一支給定股票第`i`天的價(jià)格。你只能選擇某一天買入這只股票，并選擇在未來的某一個(gè)不同的日子賣出該股票。設(shè)計(jì)一個(gè)算法來計(jì)算你所能