滚动数组Rolling Array

如果状态依赖关系只在相邻的几层之间，则可以使用滚动数组进行优化，滚动数组可以让空间复杂度降维。

题型1：数字三角形

给定一个三角形，找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。
image.png

  1. class Solution {
  2. public:
  3.     int minimumTotal(vector<vector<int>>& triangle) {
  4.         if(triangle.size() == 0)
  5.             return 0;
  6.         int len = triangle.size();
  8.         int dp[2][len];
  11.         dp[0][0] = triangle[0][0];
  13.         for(int i = 1; i < len; i++)
  14.         {
  15.             dp[i % 2][0] = dp[(i - 1) % 2][0] + triangle[i][0];
  16.             dp[i % 2][i] = dp[(i - 1) % 2][i - 1] + triangle[i][i];
  18.             for(int j = 1; j < i; j++)
  19.             {
  20.                 dp[i % 2][j] = min(dp[(i - 1) % 2][j - 1], dp[(i - 1) % 2][j]) 
  21.                     + triangle[i][j];
  22.             }
  23.         }
  25.         int minPath = dp[(len - 1) % 2][0];
  26.         for(int i = 1; i < len; i++)
  27.         {
  28.             minPath = min(minPath, dp[(len - 1) % 2][i]);
  29.         }
  30.         return minPath;
  31.     }
  32. };

用两行滚动数组记录各个点的最短路径