什么是滾動陣列

　　　　簡單來說，滾動陣列就是一種具有短暫記憶力的陣列，它會犧牲時間來節省空間，用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博客_滾動陣列

標籤：C

上一篇：分治的理解

下一篇：本次秋招最差面試體驗給到華為！