【算法】动态规划

目录

1.解决什么类型问题

1.1 计数问题

1.2 极值问题

2.特性

2.1 重复子问题

2.2 无后效性

2.3 最优化子结构

3.过程步骤

3.1 设计步骤

3.2 练习反馈

Ex 1 最大子数组之和（easy）

---

1.解决什么类型问题

1.1 计数问题

如最典型的青蛙跳，也就是斐波那契数列、棋盘路径问题、

还有组合公式,不重复组合（ Combination ），c(n, m)从n个选手中选出m个出道～（101哈哈哈哈哈），有多少种可能性？这个问题可以分解为两个子问题，根据最后一个人能不能进组合有两种可能：

最后一个人出道，剩余席位是m-1, 子问题是c(n-1, m-1)

最后一个人不能出道，剩余席位还是m，子问题是c(n-1，m)

c(n, m) = { c(n-1, m-1) + c(n-1, m) , if n > 1 and m > 1 and n >= m { n , if m = 1 { 1 , if n = 1

这一类问题通常递推公式是子问题的和，c(n, m) =c(n-1, m-1) + c(n-1, m)，边界就是m=1或者n=1。

1.2 极值问题

如背包问题，就是多阶段最优决策。一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条决策路径。
    初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态

如棋盘最大和（最小和），从(0,0) 到 （n-1,n-1）路上数值最大和

这一类问题通常递推公式是子问题max、min值，如上题c[i][j] = max(c[i-1][j], c[i][j-1])  +  a[i][j];

还有最长递增子序列、最少找零问题、最大子数组等等，更多问题和详情可见top15动态规划

2.特性

2.1 重复子问题

如下图所示，求解斐波那契数列时，同一个子问题（图中划圈）的解重复求解，会导致组合爆炸，重复计算，为了解决这个问题，可以通过记忆化memoization解决，即记录子问题的解

2.2 无后效性

下一时刻的状态只与当前状态有关，而和当前状态之前的状态无关，当前的状态是对以往决策的总结，

棋盘最大和问题，如果当前状态是处于dp[i][j]上，下一时刻的状态就是dp[i+1][j]，和dp[i][j+1]，这两个状态仅和当前状态（到【i，j】的最大值）有关，对于dp[i-1][j-1]这些之前的状态不关心。

2.3 最优化子结构

假设为了解决某一优化问题，需要依次作出n个决策D1，D2，…，Dn，如若这个决策序列是最优的，对于任何一个整数k，1 < k < n，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，Dk+2，…，Dn也是最优的。

3.过程步骤

反复读取数据、计算数据、存储数据。实现方式有两种：递归和循环迭代

1. 把原问题递归分割成多个更小的問題。（recurrence递归 分治）
   1-1. 子問題與原問題的求解方式皆類似。（optimal sub-structure最优子结构）
   1-2. 子問題會一而再、再而三的出現。（overlapping sub-problems重复子问题）
2. 设计计算过程：
   2-1. 确认每个问题有哪些子问题。（recurrence 递归）
   2-2. 确认总共有哪些问题。（state space 状态空间）
   2-3. 把问题一一对应到表格。（lookup table 记忆表）
   2-4. 确定问题的计算顺序。（computational sequence 计算顺序）
   2-5. 确定初始值、计算范围。（initial states / boundary 初始状态／计算边界）
3. 事件，主要有两种方式：
   3-1. Top-down 自上而下   递归
   3-2. Bottom-up 自下而上   循环迭代

	递归	迭代
优点	代码可读性高，易理解 不必考虑子问题的依赖关系和计算顺序 当仅需求解一部分子问题时 更快	代码更短 没有递归负载，执行更快 滑动窗口
缺点	不能使用滑动窗口 可能栈溢出	可读性差，不直观 需注意子问题依赖关系和计算顺序

3.1 设计步骤

(1)划分阶段
(2)确定状态空间和状态变量  通常是数组（1维或多维）下标指决策，元素 指状态
(3)确定决策并写出状态转移方程  递推公式
(4)寻找边界条件

3.2 练习反馈

一般去leetCode去练习

Ex 1 最大子数组之和（leet 53 easy）

问题：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

分析：是上述的第二类极值问题，递推公式为 subsum[i] = max{subsum[i-1],0} + nums[i]，边界就是i属于[0,n)，计算顺序是从0到n-1

优化：空间优化，可以用一维数组subsum[i] 保存 包含第i个元素的连续子数组的最大和，但由于i+1只与第i个元素有关（无后效性），可以退化成用一个变量保存，每次迭代更新。

    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int presum = 0;
        int result = Integer.MIN_VALUE;
        for (int i=0;i<n;i++) {
            int cursum = Math.max(presum, 0) + nums[i]; // 递推
            if (cursum > result) result = cursum;    // 更新最大和
            presum = cursum;    // 更新前一状态
        }
        return result;
    }

复杂度：时间T(n) = O(n)，空间S(n)=O(n)

Ex 2 不同路径 II （leet 63 Medium）

问题：网格中的障碍物和空位置分别用 1 和 0 来表示。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角，从左上角到右下角将会有多少条不同的路径？

分析：上述的第一类计数问题， 递推公式如下；由于每个元素依赖上，左元素，计算顺序应 自上往下，自左向右；边界就是二维数组边界，不越界。

dp[i][j] = 0; if grid[i][j]==1

dp[i][j] = dp[i-1][j] + dp[i][j-1]; if i>0 && j>0

dp[i][j] = dp[i][j-1] if i==0

dp[i][j] = dp[i-1][j] if j==0

优化：由于每次只依赖上一行和当前行（无后效），状态空间可以仅保存两行，滚动数组，空间从n2优化到n

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid.length==0 || obstacleGrid[0].length == 0) return 0;
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] dp = new int[2][n];
        int curline = 0;
        // 自上往下
        for (int i=0;i<m;i++) {
            // 自左往右
            for (int j=0;j<n;j++) {
                int cur = 0;
                if (obstacleGrid[i][j]==0) { // 障碍物直接为0 不能到达
                    if (i==0 && j==0) {
                        cur = 1;             // 初始值
                    } else {
                        if (i>0) {           //迭代 边界检查
                            cur += dp[1-curline][j]; // 上方元素
                        }
                        if (j>0) {
                            cur += dp[curline][j-1]; // 左边元素
                        }
                    }
                }
                dp[curline][j] = cur;
            }
            curline = 1 - curline;
        }
        return dp[1-curline][n-1];
    }

复杂度：时间T(n) = O(n2)，空间S(n)=O(n)