算法分析，備忘錄方法的遞歸方式是自頂向下的，動態(tài)規(guī)劃算法的遞歸方式是自底向上的，想問一下？分治算法和動態(tài)規(guī)劃有什么不同和聯(lián)系？1。分治法和動態(tài)規(guī)劃法有一個主要的共同點(diǎn)：1）二者都要求原問題具有最優(yōu)子結(jié)

算法分析，備忘錄方法的遞歸方式是自頂向下的，動態(tài)規(guī)劃算法的遞歸方式是自底向上的，想問一下？

分治算法和動態(tài)規(guī)劃有什么不同和聯(lián)系？

1。分治法和動態(tài)規(guī)劃法有一個主要的共同點(diǎn)：1）二者都要求原問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，即對原問題進(jìn)行分治，將原問題分解成若干個較小的子問題（小到很容易）作為待解程序的子問題。然后將子問題的解進(jìn)行組合，形成原問題的解。

2、分治法與動態(tài)規(guī)劃實(shí)現(xiàn)方法：①分治法通常采用遞歸求解。

②動態(tài)規(guī)劃一般采用自下而上的迭代法求解，也可采用帶記憶函數(shù)的遞歸法自上而下求解。

3、分治法與動態(tài)規(guī)劃的主要區(qū)別如下：1。分治法把分解的子問題看作是獨(dú)立的。

②在動態(tài)規(guī)劃中，分解的子問題被理解為相互關(guān)聯(lián)和重疊的部分。

【編譯原理】自頂向下LL（1）分析中，消除左遞歸和提取左因子的目的是什么？

通常，LL（1）是通過函數(shù)遞歸實(shí)現(xiàn)的

]例如，語法：a-> a | a

代碼實(shí)現(xiàn)是：[function a（）

{

a（）

match（”）

term（a）]}

！]這樣就可以看到死循環(huán)了…

消除了左遞歸后的語法

a-> AA“

a”-> AA“

]這個問題可以避免

公因子就是剛剛提出的就像我上面說的，避免程序回溯和消除歧義。

為什么歸并排序merge sort不需要像動態(tài)規(guī)劃的問題一樣考慮每一種劃分情況？

為什么合并排序不需要像動態(tài)規(guī)劃的問題一樣考慮每個分區(qū)？

遞歸的重要性不言而喻。它是許多算法的基礎(chǔ)，例如具有分治思想的算法（合并排序、二叉搜索）、遍歷二叉樹的算法，或者求解數(shù)學(xué)遞歸（斐波那契序列、n的階乘）、回溯、動態(tài)規(guī)劃等算法，當(dāng)談到遞歸時，總是有點(diǎn)混亂。理論上更容易理解，但當(dāng)涉及到更復(fù)雜的遞歸算法時，很難想象遞歸是如何在計(jì)算機(jī)中實(shí)現(xiàn)的。經(jīng)過一步一步的調(diào)試，我們終于明白了，所以我們先把這個過程記錄下來。

：就是利用分而治之的思想，排序的過程就是先把數(shù)組分成左右兩部分，分別排序，然后把有序的兩個數(shù)組組合成一個有序的數(shù)組。

重點(diǎn)分析merge在代碼中的作用，sort是一個遞歸函數(shù)，第一個是終止條件P>=R，遞歸必須有終止條件，否則會陷入循環(huán)，最終導(dǎo)致堆棧溢出。為什么堆棧溢出？實(shí)際上，底部的遞歸調(diào)用是按下并退出線程堆棧的操作。每次調(diào)用都會按一次堆棧，并記錄相關(guān)的局部變量信息。線程堆棧的內(nèi)存非常有限。如果遞歸調(diào)用是無限的，它將很快消耗所有的內(nèi)存資源，并最終導(dǎo)致內(nèi)存溢出。

下兩個調(diào)用merge#sort?C函數(shù)本身也是一個遞歸調(diào)用，兩個遞歸調(diào)用分別編號為?1和?2。在本例中，數(shù)組中有六個元素（下標(biāo)0-5）要排序，那么如何將它們從堆棧中按出？如下圖所示：