概述

在算法的最終結果只用到本層與上一層的結果時， 可以使用滾動數組思想。

簡單的理解就是每次都使用固定的幾個存儲空間達到壓縮節省存儲空間的作用， 主要用在遞推算法中。

示例1： 爬樓梯問題

假設你正在爬樓梯。需要 n 階你才能到達樓頂。每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

由題可知， 在爬上第 n 階樓梯時，可以爬 1 個或 2 個臺階， 即爬上最后一階臺階時，總辦法數 = 最后一階臺階是 n-1 階與 最后一階臺階是 n-2 階的辦法數的和， 即狀態轉移方程為：
$f(n)=f(n?1)+f(n?2)$
接下來推算邊界條件，即：
$f(1)=1,f(2)=2$
即最后的代碼為：

public int climbStairs(int n) {if (n==1) {return 1;}if (n==2) {return 2;}return climbStairs(n-1)+climbStairs(n-2); }

這種做法的好處就是比較直觀，但是方法的時間復雜度為 $O(2^n)$。
所以這里可以用到滾動數組的思想來進行優化:

public int climbStairs(int n) {int left = 0, right = 0, sum = 0;for (int i = 1;i<=n;i++) {left = right;right = sum;sum = left + right;}return sum; }

這樣做的時間復雜度就降到了$O(n)$。

示例2： 最大子序和

給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。

由題可知， 第 n 個元素的結果與第 n-1 個元素的結果以及第 n 個元素的大小有關系， 即：
$f(n)=Max(f(n?1)+nums[n],nums[n])$
所以， 問題的解法即遍歷數組中所有元素的并求出這些元素對應結果的最大值即可:

public int maxSubArray(int[] nums) {int prev = 0;int max = nums[0];for (int i:nums) {prev = Math.max(prev+i, i);max = Math.max(prev, max);}return max; }

總結

以上是生活随笔為你收集整理的递推算法之滚动数组思维方式的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。