动态规划：空间优化技巧以及接龙型动态规划

左手的ㄟ右手 2022-11-11 13:18 175阅读 0赞

## 空间优化方法 ##

### 滚动数组 ###

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

### 坐标型动态规划使用滚动数组 ###

数字三角形的状态转移方程为  
dp\[i\]\[j\] = min(dp\[i - 1\]\[j\], dp\[i - 1\]\[j - 1\]) + A\[i\]\[j\]

滚动数组优化之后为  
dp\[i % 2\]\[j\] = min(dp\[(i - 1) % 2\]\[j\], dp\[(i - 1) % 2\]\[j - 1\]) + A\[i\]\[j\]

因为每一步只与他的前一步有关，所以前面的数组我们可以重复使用，而不需要开辟新的空间。

随着滚动数组优化，我们需要改变的地方：

//原来的版本，详情请看动态规划入门：
    
    public int minimumTotal(int[][] triangle) { 
            if (triangle == null || triangle.length == 0) { 
                return -1;
            }
            if (triangle[0] == null || triangle[0].length == 0) { 
                return -1;
            }
            
            int n = triangle.length;
            int[][] f = new int[n][n];
            
            // initialize: 三角形的左边和右边要初始化
            // 因为他们分别没有左上角和右上角的点
            f[0][0] = triangle[0][0];
            for (int i = 1; i < n; i++) { 
                f[i][0] = f[i - 1][0] + triangle[i][0];
                f[i][i] = f[i - 1][i - 1] + triangle[i][i];
            }
            
            // function: f[i][j] = Math.min(f[i - 1][j], f[i - 1][j - 1]) + triangle[i][j];
            for (int i = 1; i < n; i++) { 
                for (int j = 1; j < i; j++) { 
                    f[i][j] = Math.min(f[i - 1][j], f[i - 1][j - 1]) + triangle[i][j];
                }
            }
            // answer: 最后一层的任意位置都可以是路径的终点
            int best = f[n - 1][0];
            for (int i = 1; i < n; i++) { 
                best = Math.min(best, f[n - 1][i]);
            }
            return best;
        }
    
    //滚动数组版本：
    public int minimumTotal(int[][] triangle) { 
            if (triangle == null || triangle.length == 0) { 
                return -1;
            }
            if (triangle[0] == null || triangle[0].length == 0) { 
                return -1;
            }
            
            int n = triangle.length;
            //空间负责度进行了降纬 n => 2
            int[][] f = new int[2][n];
            
            f[0][0] = triangle[0][0];
            // 因为数组空间不能够直接初始化，我们需要在动态的过程中初始化
            for (int i = 1; i < n; i++) { 
            	f[i % 2][0] = f[(i - 1) % 2][0] + triangle[i][0];
            	f[i % 2][i] = f[(i - 1) % 2][i - 1] + triangle[i][i];
                for (int j = 1; j < i; j++) { 
                    f[i % 2][j] = min(f[(i - 1) % 2][j], f[(i - 1) % 2][j - 1]) + triangle[i][j]
                }
            }
            // answer: 最后一层的任意位置都可以是路径的终点
            int best = f[(i - 1) % 2][0];
            for (int i = 1; i < n; i++) { 
                best = Math.min(best, f[(i - 1) % 2][i]);
            }
            return best;
        }

从上面的不同的两个版本我们可以知道最大的区别在于初始化，因为数组空间不能够直接初始化，所以我们需要在动态的过程中初始化。

**那么能否两个维度一起滚动呢?**  
dp\[i\]\[j\] = min(dp\[i - 1\]\[j\], dp\[i - 1\]\[j - 1\]) + A\[i\]\[j\] =>  
dp\[i % 2\]\[j % 2\] = min(dp\[(i - 1) % 2\]\[j % 2\], dp\[(i - 1) % 2\]\[(j - 1) % 2\]) + A\[i\]\[j\]

> 不可以，因为j不是全局单调递增的，所以他的数据需要被保存，而 i 是全局单调递增的。

所以我们可以得出，滚动数组只可以滚动一个维度，不能滚动两个维度。

实例：  
[斐波那契数列][Link 1]

class Solution { 
        public int fib(int n) { 
            int[] dp = new int[3];
            dp[0%3] = 0;
            dp[1%3] = 1; 
            for(int i = 2 ; i <= n; i++){ 
                dp[i % 3] = (dp[(i - 1) % 3] +  dp[(i - 2) % 3]) % 1000000007;
            
            }    
            return dp[n%3];
        }
    }

总结：

*  滚动数组滚动的是第一重循环的变量，而不是第二重甚至第三重
 *  滚动数组也只能滚一个维度
 *  不能两个维度一起滚动

## 接龙型动态规划 ##

> 属于“坐标型”动态规划的一种 题型一般是告诉你一个接龙规则，让你找最长的龙

经典例题：  
[LeetCode 300. 最长递增子序列][LeetCode 300.]

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，\[3,6,2,7\] 是数组 \[0,3,1,6,2,2,7\] 的子序列。

例子1:
    
    输入：nums = [10,9,2,5,3,7,101,18]
    输出：4
    解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

利用动规四要素分析：

state: 
    dp[i] 表示以第 i 个数为龙尾的最长的龙有多长 
    
    function: 
    dp[i] = max{ dp[j] + 1}, j < i && nums[j] < nums[i] 
    
    initialization://每个位置都可以是龙头 
    dp[0..n-1] = 1
    
    answer:
    max{ dp[0..n-1]}

**Follow up:** 求具体的方法

倒推法  
记录每个状态的最优值是从哪个前继状态来的 通常需要一个和状态数组同样维度的数组 prev\[i\] 记录 使得 dp\[i\] 获得最优值的那个 j 是谁 j 是方程 dp\[i\] = max\{dp\[j\] + 1\} 里的j

[最长上升连续子序列 II][II]  
描述：  
给定一个整数矩阵. 找出矩阵中的最长连续上升子序列, 返回它的长度. 最长连续上升子序列可以从任意位置开始, 向上/下/左/右移动.

输入: 
        [
          [1, 2, 3, 4, 5],
          [16,17,24,23,6],
          [15,18,25,22,7],
          [14,19,20,21,8],
          [13,12,11,10,9]
        ]
    输出: 25
    解释: 1 -> 2 -> 3 -> 4 -> 5 -> ... -> 25 (由外向内螺旋)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU1MjIxMjM5_size_16_color_FFFFFF_t_70]

[LeetCode 368.最大整除子集][LeetCode 368.]

描述：

给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 Sj % Si = 0。

如果有多个目标子集，返回其中任何一个均可。

示例 1:
    
    输入: [1,2,3]
    输出: [1,2] (当然, [1,3] 也正确)

class Solution { 
        public List<Integer> largestDivisibleSubset(int[] nums) { 
            if (nums == null || nums.length == 0) { 
                return new ArrayList();
            }
            
            Arrays.sort(nums);
            int n = nums.length;
            HashMap<Integer, Integer> dp = new HashMap();
            HashMap<Integer, Integer> prev = new HashMap();
            
            for (int i = 0; i < n; i++) { 
                dp.put(nums[i], 1);
                prev.put(nums[i], -1);
            }
            
            int lastNum = nums[0];
            for (int i = 0; i < n; i++) { 
                int num = nums[i];
                for (Integer factor : getFactors(num)) { 
                    if (!dp.containsKey(factor)) { 
                        continue;
                    }
                    if (dp.get(num) < dp.get(factor) + 1) { 
                        dp.put(num, dp.get(factor) + 1);
                        prev.put(num, factor);
                    }
                }
                if (dp.get(num) > dp.get(lastNum)) { 
                    lastNum = num;
                }
            }
            
            return getPath(prev, lastNum);
        }
        
        private List<Integer> getPath(HashMap<Integer, Integer> prev, int lastNum) { 
            List<Integer> path = new ArrayList();
            while (lastNum != -1) { 
                path.add(lastNum);
                lastNum = prev.get(lastNum);
            }
            Collections.reverse(path);
            return path;
        }
        
        private List<Integer> getFactors(int num) { 
            List<Integer> factors = new ArrayList();
            if (num == 1) { 
                return factors;
            }
            int factor = 1;
            while (factor * factor <= num) { 
                if (num % factor == 0) { 
                    factors.add(factor);
                    if (factor != 1 && num / factor != factor) { 
                        factors.add(num / factor);
                    }
                }
                factor++;
            }
            return factors;
        }
    }

[Link 1]: https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/
[LeetCode 300.]: https://leetcode-cn.com/problems/longest-increasing-subsequence/
[II]: https://www.lintcode.com/problem/longest-continuous-increasing-subsequence-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU1MjIxMjM5_size_16_color_FFFFFF_t_70]: /images/20221022/ef85ab65721c4fb08830912503aa2b18.png
[LeetCode 368.]: https://leetcode-cn.com/problems/largest-divisible-subset/