一、什么是遞推

遞推算法是一種通過已知信息逐步推導未知信息的算法設計技術。遞推算法的核心思想是利用已經(jīng)計算出的結(jié)果來推導新的結(jié)果，從而避免重復計算，提高效率。

二、遞推算法的分類

遞推算法可以分為順推和逆推兩種：
順推法：從已知條件出發(fā)，逐步推算出要解決的問題的方法。它通常用于求解序列的下一項或達到某個特定狀態(tài)所需的步驟。例如，斐波那契數(shù)列的求解就可以使用順推法。

逆推法：從已知問題的結(jié)果出發(fā)，用迭代表達式逐步推算出問題的初始條件。它是順推法的逆過程，通常用于求解逆向問題或回溯問題。

三、遞推算法的特點

高效性：遞推算法避免了數(shù)據(jù)進出棧的過程，直接從邊界出發(fā)，直到求出函數(shù)值。因此，相對于遞歸算法，遞推算法通常具有更高的效率。

簡單性：遞推算法將復雜的計算過程轉(zhuǎn)化為簡單的重復步驟，使得算法易于理解和實現(xiàn)。

適用性：遞推算法適用于求解具有遞推關系的問題，如數(shù)列、動態(tài)規(guī)劃等。

四、遞推算法的應用

數(shù)列求解：遞推算法在求解數(shù)列問題中具有重要作用。例如，斐波那契數(shù)列、等差數(shù)列、等比數(shù)列等都可以通過遞推算法來求解。

動態(tài)規(guī)劃：動態(tài)規(guī)劃是一種解決最優(yōu)化問題的算法思想，它通常使用遞推關系來求解最優(yōu)解。遞推算法在動態(tài)規(guī)劃中具有廣泛的應用。

組合數(shù)學：遞推算法在組合數(shù)學中也有重要作用。例如，求解排列、組合、概率等問題時，經(jīng)常需要使用遞推關系來簡化計算。

——————
一般來說，在步入后面的學習中，遞推長與不同的算法搭配，如貪心，DP，矩陣乘法，數(shù)學內(nèi)容等，在此不涉及數(shù)學內(nèi)容，來鍛煉一下思維

P2943

$$f_i=\underset{j=1}{\overset{i?1}{min}}{f}_j+si{z}^2$$

考慮如何優(yōu)化

容易發(fā)現(xiàn)總代價不超過n，所以只要\(siz\)大于$\sqrt{n} $就不優(yōu),考慮保留從第i位起往前數(shù)有j個不同數(shù)的區(qū)間左端點，也就是分為j個線段，每個線段新出現(xiàn)一個數(shù)

如何動態(tài)維護呢，顯然我們可以遞推來做這件事，無外乎3種情況
1.此時還沒有出現(xiàn)$\sqrt{n} $種顏色，直接添加

2.這種顏色之前沒有出現(xiàn)過，之間頂?shù)粢粋€

3.找到這種顏色在第\(pos\)段出現(xiàn)過，則后面幾段不變，前面幾段前移

$$f_i=\underset{j=1}{\overset{\sqrt{n}}{min}}{f}_{p_j?1}+si{z}^2$$

T386375

遞推/DP + 貪心

先不考慮未來的歷史，考慮第i個字符
1.之前還沒有出現(xiàn)過\(f_i=f_{i-1}*2+1\)

2.之前出現(xiàn)過，考慮算重了哪些，設此字符上一次出現(xiàn)的位置為\(la\),\(f_i=f_{i-1}*2-f_{la-1}\)

再考慮未來的歷史
1.首先會發(fā)現(xiàn)f是單調(diào)遞增的

2.所以貪心取上一次出現(xiàn)字符最靠前的字符

for(int i=a.size()+1;i<=a.size()+m;i++)
	{
		int w=1e9,p;
		for(int j=1;j<=k;j++)
		  if(la[j]<w) w=la[j],p=j;
		if(la[p]) f[i]=2*f[i-1]-f[la[p]-1];
		else f[i]=2*f[i-1]+1;
		la[p]=i;f[i]=(f[i]+P)%P;
	}

P4965