什麼是滾動數組

　　　　簡單來說，滾動數組就是一種具有短暫記憶力的數組，它會犧牲時間來節省空間，用size=3的數組來“存儲”30000個數據。這麼說有點離譜、抽象，畢竟a[3]怎麼存儲a[30000]裡面的東西呢。這就是滾動數組的特性，即只記錄少量的後續需要使用的數據，而將之前用過且不再需要調用的數據拋棄、覆蓋，這樣就將a[30000]中不要的數據所占的空間節省出來，以達到a[3]就能達成的任務目標。

滾動數組的核心：取餘

　　　　在開始學習C語音的時候，接觸到了一個新的數學運算符：取餘%，和除號 / 類似的是都多用在特殊的迴圈或者是取一串數字的某一位，除法多取高位，取餘多取低位。在滾動數組中，取餘用於數組下標的動態改變，以達到[3]存[30000]的效果，例如：

int m=30000;//一個原先大的數據空間
int n=3;//所需要的一個滾動數組空間
void fun()
{

    for (int i = 0; i < m; i++)
    {
        d[i % n] = d[(i - 1) % n] + d[(i - 2) % n];
    }
}

　　　　通過取餘的特點可以看出，動態數組在取模和迴圈的作用下只用3個空間就可以做到存儲30000個數據的作用。

使用情況（淺提動態規劃）

　　那什麼時候使用呢？

1. 在不在意時間，只需要節省空間的情況。滾動數組的本質是通過for迴圈多次覆蓋不用的數值，增加了時間，又使用取餘動態改變數組下標，節省了空間。
2. 多用於動態規劃問題（Dynamic Programing，DP）。　　

　　在這不得不說到動態規劃問題，但由於篇幅所限，在此僅淺談一下，後續有緣更新。DP主要用於求解以時間劃分階段的動態過程的優化問題，但是一些與時間無關的靜態規劃(如線性規劃、非線性規劃)，只要人為地引進時間因素，把它視為多階段決策過程，也可以用動態規劃方法方便地求解。

    多階段決策過程的特點是每個階段都要進行決策，具有n個階段的決策過程的策略是由n個相繼進行的階段決策構成的決策序列。由於前階段的終止狀態又是後一階段的初始狀態，因此確定階段最優決策不能只從本階段的效應出發，必須通盤考慮，整體規劃。就是說，階段k的最優決策不應只是本階段的最優，而必須是本階段及其所有後續階段的總體最優。

　　　而DP 的有最重要的兩個理論--最優化原理和無後效性原則：

• 最優化理論，即最優子問題。其思想總結就是最優策略的任何一部分子策略也必須是最優的。舉個例子，挑選一段回家的最短路程（最優策略），路上會經過的各種檢查點（階段），該路的任何一個地方到家的路徑也是同階段到家路徑的最短路徑（子問題最優）。詳情可見：動態規劃的基本概念和最優化原理_Vasari的博客-CSDN博客_動態規劃的最優化原理
• 無後效原則。某階段的狀態旦確定，則此後過程的演變不再受此前各狀態及決策的影響。也就是說，“未來與過去無關”（非常好理解）。更具體消息的可以參考：動態規劃——無後效性及如何消除後效性_大司馬學編程的博客-CSDN博客_動態規劃 無後效性裡面指出一個很有意思的點：通過二維數組區分、寄存指定狀態，解決後效性問題。

例題說明

　　斐波那契數列

1. 因為乘數指定，即只有一條路能走，故符合最優原理。
2. 乘積固定，沒有其它因素影響，所以符合無後效性原則。

因此可以使用滾動數組方法，代碼：

 1 void func2()
 2 {
 3     int d[3];
 4     d[0] = 1;
 5     d[1] = 1;
 6     for (int i = 0; i < 100; i++)
 7     {
 8         d[i % 3] = d[(i - 1) % 3] + d[(i - 2) % 3];
 9     }
10     printf("%d", d[99 % 3]);
11 }

　　01背包

1. 整體最優是由一步步的子問題最優組成，即n個空間的包最優解是由1~n-1個空間背包的最優解組合而成，故符合最優原理。
2. 每個數值固定，無論前面問題是怎樣解，後面背包總空間不變，往後的任何決策都不會改變。故符合無後效性。

因此可以使用滾動數組方法，代碼：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1e3+10;
 4 int t,n,v;
 5 int dp[maxn];
 6 int value[maxn];
 7 int weight[maxn];
 8 int main()
 9 {
10     scanf("%d",&t);
11     while(t--)
12     {
13         memset(dp,0,sizeof dp);
14         scanf("%d %d",&n,&v);
15         for(int i = 1;i <= n;i++)
16             scanf("%d",&value[i]);
17         for(int i = 1;i <= n;i++)
18             scanf("%d",&weight[i]);
19         // for(int i = 1;i <= n;i++)    原始二維dp方程
20         //     for(int j = 0;j <= v;j++)
21         //     {
22         //         if(j >= weight[i])        //若取得下，則可以選擇取或不取
23         //             dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
24         //         else    
25         //             dp[i][j]=dp[i-1][j];
26         //     }
27         for(int i = 1;i <= n;i++)    //使用滾動數組優化後的dp方程
28             for(int j = v;j >= weight[i];j--)    //倒序保證數據更新的有序性，保證只取一次，正序則是完全背包的寫法
29                 dp[j]=max(dp[j],dp[j - weight[i]] + value[i]);
30         printf("%d\n",dp[v]);
31     }
32     return 0;
33 }

<-------------------------------------------------------------------------------------------->

最後，滾動數組只是動態問題中的一小部分，後續還有更多有趣的知識，例如動態問題和搜索、分治法的聯繫和區別，隨緣更新。By the way，更新這篇時正趕上國慶，擺了幾天，當我正常學習的時候，電腦開擺了，這麼點字，它瘋狂藍屏、黑屏，問題是沒保存，導致寫了好幾次，有些小細節因為寫太多煩了，就沒打，現在反而忘了，華碩天選2，你惡事做盡！！！！

文章部分節選：

動態規劃之滾動數組 - shawchakong - 博客園 (cnblogs.com)

滾動數組（簡單說明）_儒rs的博客-CSDN博客_滾動數組