关于算法-数据结构:浅谈动态规划

公众号目前与「动静布局」相干系列包含：曾经完结的「动静布局 - 门路问题」和正在更新「动静布局 - 背包问题」。

这都是默认大家有肯定的「动静布局」意识的系列文章。

但事实上，可能有不少同学是刚接触算法，还处于只会应用「奢侈 / 暴力解法」来解决算法问题的阶段，对于「动静布局」并不理解。

因而我特意翻出来大略是我六七年写的文章（过后更多作为学习笔记），来帮忙大家对「动静布局」有个根本意识。

须要阐明的是，本文只停留在对「动静布局」的感性认识，并没有深刻到动静布局与图论的实质关系。

因而更多的面向是算法入门读者。

以下是注释内容。

始终搞不懂「动静布局」和「记忆化搜寻」之间的区别。

总感觉动静布局只是单纯的难在于对“状态”的形象定义和“状态转移方程”的推导，并无具体的法则可循。

但从算法逐渐优化角度而言，动静布局更多是从如下形式进行演变：

❝

暴力递归 -> 记忆化搜寻 -> 动静布局。

❞

甚至能够说简直所有的「动静布局」都能够通过「暴力递归」转换而来，前提是该问题是一个“无后效性”问题。

从对“个例”的奢侈枚举做法，演变为对“汇合”的枚举做法。

所谓的“无后效性”是指：当某阶段的状态一旦确定，尔后的决策过程和最终后果将不受此前的各种状态所影响。

可简略了解为当编写好一个递归函数之后，当可变参数确定之后，后果是惟一确定的。

可能你还是对什么是“无后效性”问题感到难以了解。没关系，咱们再举一个更具象的例子，这是 LeetCode 62. Unique Paths：给定一个的矩阵，从左上角作为终点，达到右下角共有多少条门路（机器人只能往右或者往下进行挪动）。

这是一道经典的「动静布局」入门题目，也是一个经典的“无后效性”问题。

它的“无后效性”体现在：当给定了某个状态（一个具体的的矩阵和某个终点，如 (1,2)），那么从这个点达到右下角的门路数量就是齐全确定的。

而与如何达到这个“状态”无关，与机器人是通过点 (0,2) 达到的 (1,2)，还是通过 (1,1) 达到的 (1,2) 无关。

这就是所谓的“无后效性”问题。

当咱们尝试应用「动静布局」解决问题的时候，首先要关注该问题是否为一个“无后效性”问题。

常常咱们面对一个问题，即便咱们明确晓得了它是一个“无后效性”问题，它能够通过「动静布局」来解决。咱们还是感觉难以动手。

这时候我的倡议是，先写一个「暴力递归」的版本。

还是以刚刚说到的 LeetCode 62. Unique Paths 举例：

class Solution {public int uniquePaths(int m, int n) {return recursive(m, n, 0, 0);
    }

    private int recursive(int m, int n, int i, int j) {if (i == m - 1 || j == n - 1) return 1;
        return recursive(m, n, i + 1, j) + recursive(m, n, i, j + 1);
    }
}

当我还不晓得如何应用「动静布局」求解时，我会设计一个递归函数。

函数传入矩阵信息和机器人以后所在的地位，返回在这个矩阵里，从机器人所在的地位登程，达到右下角有多少条门路。

有了这个递归函数之后，那问题其实就是求解：求解从 (0,0) 到右下角的门路数量。

接下来，实现这个函数：

Base case: 因为题目明确了机器人只能往下或者往右两个方向走，所以能够定下来递归办法的 base case 是当曾经处于矩阵的最初一行或者最初一列，即只一条路能够走。
其余状况：机器人既能够往右走也能够往下走，所以对于某一个地位来说，达到右下角的门路数量等于它左边地位达到右下角的门路数量 + 它下方地位达到右下角的门路数量。即 recursive(m,n,i+1,j) + recursive(m,n,i,j+1)，这两个地位都能够通过递归函数进行求解。

其实到这里，咱们曾经求解了这个问题了。

但这种做法还有个重大的“性能”问题。

如果将咱们上述的代码提交到 LeetCode，会失去 timeout 的后果。

可见「暴力递归」的解决方案“很慢”。

咱们晓得所有递归函数的实质都是“压栈”和“弹栈”。

既然这个过程很慢，咱们能够通过将递归版本暴力解法的改为非递归的暴力解法，来解决 timeout 的问题吗？

答案是不行，因为导致 timeout 的起因不在于应用“递归”伎俩所带来的老本。

而在于在计算过程，咱们进行了屡次的反复计算。

咱们尝试开展递归过程第几步来看看：

不难发现，在递归开展过程会遇到很多的反复计算。

随着咱们整个递归过程的开展，反复计算的次数会呈倍数增长。

这才是「暴力递归」解决方案“慢”的起因。

既然是反复计算导致的 timeout，咱们天然会想到将计算结果进行“缓存”的计划：

class Solution {private int[][] cache;

    public int uniquePaths(int m, int n) {cache = new int[m][n];
        for (int i = 0; i < m; i++) {int[] ints = new int[n];
            Arrays.fill(ints, -1);
            cache[i] = ints;
        }
        return recursive(m, n, 0, 0);
    }

    private int recursive(int m, int n, int i, int j) {if (i == m - 1 || j == n - 1) return 1;
        if (cache[i][j] == -1) {if (cache[i + 1][j] == -1) {cache[i + 1][j] = recursive(m, n, i + 1, j);
            }
            if (cache[i][j + 1] == -1) {cache[i][j + 1] = recursive(m, n, i, j + 1);
            }
            cache[i][j] = cache[i + 1][j] + cache[i][j + 1];
        }
        return cache[i][j];
    }
}

对「暴力递归」过程中的两头后果进行缓存，确保雷同的状况只会被计算一次的做法，称为「记忆化搜寻」。

做了这样的改良之后，提交 LeetCode 曾经能 AC 并失去一个不错的评级了。

咱们再细想一下就会发现，其实整个求解过程，对于每个状况（每个点）的拜访次数并没有产生扭转。

只是从「以前的每次拜访都进行求解」改良为「只有第一次拜访才真正求解」。

事实上，咱们通过查看 recursive() 办法就能够发现：

当咱们求解某一个点的答案时，其实是依赖于和。

也就是每求解一个点的答案，都须要拜访两个点的后果。

这种状况是因为咱们采纳的是“自顶向下”的解决思路所导致的。

咱们无奈直观确定哪个点的后果会在什么时候被拜访，被拜访多少次。

所以咱们不得不应用一个与矩阵雷同大小的数组，将所有两头后果“缓存”起来。

换句话说，「记忆化搜寻」解决的是反复计算的问题，并没有解决后果拜访机会和拜访次数的不确定问题。

对于「记忆化搜寻」最初再说一下。

网上有不少博客和材料在编写「记忆化搜寻」解决方案时，会编写相似如下的代码：

class Solution {private int[][] cache;

    public int uniquePaths(int m, int n) {cache = new int[m][n];
        for (int i = 0; i < m; i++) {int[] ints = new int[n];
            Arrays.fill(ints, -1);
            cache[i] = ints;
        }
        return recursive(m, n, 0, 0);
    }

    private int recursive(int m, int n, int i, int j) {if (i == m - 1 || j == n - 1) return 1;
        if (cache[i][j] == -1) {cache[i][j] = recursive(m, n, i + 1, j) + recursive(m, n, i, j + 1);
        }
        return cache[i][j];
    }
}

能够和我下面提供的解决方案作比照。次要区别在于 if (cache[i][j] == -1) 的判断外面。

在我提供解决方案中，会在计算 cache[i][j] 时，尝试从“缓存”中读取 cache[i+1][j] 和 cache[i][j+1]，确保每次调用 recursive() 都是必须的，不反复的。

网上大多数的解决方案只会在外层读取“缓存”，在真正计算 cache[i][j] 的时候并不采取先查看再调用的形式，间接调用 recursive() 计算子问题。

尽管两者相比与间接的「暴力递归」都大大减少了计算次数（recursive() 的拜访次数），但后者的计算次数显然要比前者高上不少。

你可能会感觉反正都是“自顶向下”，两者应该没有区别吧？

为此我提供了以下试验代码来比拟它们对 recursive() 的调用次数：

class Solution {public static void main(String[] args) {Solution solution = new Solution();
        solution.uniquePaths(15, 15);
    }
    
    private int[][] cache;
    private long count; // 统计 递归函数 的调用次数

    public int uniquePaths(int m, int n) {cache = new int[m][n];
        for (int i = 0; i < m; i++) {int[] ints = new int[n];
            Arrays.fill(ints, -1);
            cache[i] = ints;
        }
        // int result = recursive(m, n, 0, 0); // count = 80233199
        // int result = cacheRecursive(m, n, 0, 0); // count = 393
        int result = fullCacheRecursive(m, n, 0, 0); // count = 224
        System.out.println(count);
        return result;
    }

    // 齐全缓存 
    private int fullCacheRecursive(int m, int n, int i, int j) {
        count++;
        if (i == m - 1 || j == n - 1) return 1;
        if (cache[i][j] == -1) {if (cache[i + 1][j] == -1) {cache[i + 1][j] = fullCacheRecursive(m, n, i + 1, j);
            }
            if (cache[i][j + 1] == -1) {cache[i][j + 1] = fullCacheRecursive(m, n, i, j + 1);
            }
            cache[i][j] = cache[i + 1][j] + cache[i][j + 1];
        }
        return cache[i][j];
    }

    // 只有外层缓存
    private int cacheRecursive(int m, int n, int i, int j) {
        count++;
        if (i == m - 1 || j == n - 1) return 1;
        if (cache[i][j] == -1) {cache[i][j] = cacheRecursive(m, n, i + 1, j) + cacheRecursive(m, n, i, j + 1);
        }
        return cache[i][j];
    }

    // 不应用缓存
    private int recursive(int m, int n, int i, int j) {
        count++;
        if (i == m - 1 || j == n - 1) return 1;
        return recursive(m, n, i + 1, j) + recursive(m, n, i, j + 1);
    }
}

因为咱们应用 cache 数组的目标是缩小 recursive() 函数的调用。

只有确保在每次调用 recursive() 之前先去 cache 数组查看，咱们才能够将对 recursive() 函数的调用次数减到起码。

在数据为 15 的样本下，这是和的区别，但对于一些卡常数特地重大的 OJ，尤其重要。

所以我倡议你在「记忆化搜寻」的解决方案时，采取与我一样的策略：

确保在每次拜访递归函数时先去“缓存”查看。只管这有点“不美观”，但它能施展「记忆化搜寻」的最大作用。

你可能会想，为什么咱们须要改良「记忆化搜寻」，为什么须要明确两头后果的拜访机会和拜访次数？

因为一旦咱们能明确两头后果的拜访机会和拜访次数，将为咱们的算法带来微小的晋升空间。

后面说到，因为咱们无奈确定两头后果的拜访机会和拜访次数，所以咱们不得不“缓存”全副两头后果。

但如果咱们能明确两头后果的拜访机会和拜访次数，至多咱们能够大大降低算法的空间复杂度。

这就波及解决思路的转换：从「自顶向下」到「自底向上」。

如何实现从「自顶向下」到「自底向上」的转变，还是通过具体的例子来了解。

这是 LeetCode 509. Fibonacci Number，驰名的“斐波那契数列”问题。

如果不理解什么是“斐波那契数列”，能够查看对应的维基百科。

因为斐波那契公式为：

人造适宜应用递归：

public class Solution {private int[] cache;
    public int fib(int n) {cache = new int[n + 1];
        return recursive(n);
    }

    private int recursive(int n) {if (n <= 1) return n;
        if (n == 2) return 1;
        if (cache[n] == 0) {if (cache[n - 1] == 0) {cache[n - 1] = recursive(n - 1);
            }
            if (cache[n - 2] == 0) {cache[n - 2] = recursive(n - 2);
            } 
            cache[n] = cache[n - 1] + cache[n - 2];
        }
        return cache[n];
    }
}

但这依然会有咱们之前所说的问题，这些问题都是因为间接递归是“自顶向下”所导致的。

这样的解法的时空复杂度为：每个值计算一次，应用了长度为的数组。

通过观察斐波那契公式，咱们能够发现要计算某个，只须要晓得的解和的解。

同时和的解又是已知的（base case）。

所以咱们大能够从登程，逐渐往后迭代得出的解。

因为计算某个值的解，只依赖该值的前一位的解和前两位的解，所以咱们只须要应用几个变量缓存最近的两头后果即可：

class Solution {public int fib(int n) {if (n <= 1) return n;
        if (n == 2) return 1;
        
        int prev1 = 1, prev2 = 1;
        int cur = prev1 + prev2;
        for (int i = 3; i <= n; i++) {
            cur = prev1 + prev2;
            prev2 = prev1;
            prev1 = cur;
        }
        return cur;
    }
}

这样咱们就把本来空间复杂度为的算法升高为：只是用了几个无限的变量。

但不是所有的「动静布局」都像“斐波那契数列”那么简略就能实现从“自顶向下”到“自底向上”的转变。

当然也不是毫无法则可循，尤其是咱们曾经写出了「暴力递归」的解决方案。

让咱们再次回到 LeetCode 62. Unique Paths 当中：

class Solution {public int uniquePaths(int m, int n) {// 因为咱们的「暴力递归」函数，真正的可变参数就是 i 和 j（变动范畴别离是 [0,m-1] 和 [0, n-1]）// 所以倡议一个二维的 dp 数组进行后果存储（相当于建一个表格）int[][] dp = new int[m][n];
        
        // 依据「暴力递归」函数中的 base case
        // 咱们能够间接得出 dp 中最初一行和最初一列的值（将表格的最初一行和最初一列填上）for (int i = 0; i < n; i++) dp[m - 1][i] = 1
        for (int i = 0; i < m; i++) dp[i][n - 1] = 1;
        
        // 依据「暴力递归」函数中对其余状况的解决逻辑（依赖关系）编写循环
        //（依据表格的最初一行和最初一列的值，得出表格的其余格子的值）for (int i = m - 2; i >= 0; i--) {for (int j = n - 2; j >= 0; j--) {dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
            }
        }
        
        // 最终咱们要的是 dp[0][0]（表格中左上角的地位，也就终点的值）return dp[0][0];
        
        // 原「暴力递归」调用
        // return recursive(m, n, 0, 0);
    }

    private int recursive(int m, int n, int i, int j) {
        // base case
        if (i == m - 1 || j == n - 1) return 1;
        // 其余状况
        return recursive(m, n, i + 1, j) + recursive(m, n, i, j + 1);
    }
}

不难发现，咱们甚至能够间接依据「暴力递归」来写出「动静布局」，而不须要关怀原问题是什么。

简略的「动静布局」其实就是一个“打表格”的过程：

先依据 base case 定下来表格中的一些地位的值，再依据已得出值的地位去推算其余格子的信息。

推算所用到的依赖关系，也就是咱们「暴力递归」中的“其余状况”解决逻辑。

动静布局的实质其实依然是枚举：枚举所有的计划，并从中找出最优解。

但和「暴力递归」不同的是，「动静布局」少了很多的反复计算。

因为所依赖的这些历史后果，都被存起来了，因而节俭了大量反复计算。

从这一点来说，「动静布局」和「记忆化搜寻」都是相似的。

要把历史后果存起来，必然要应用数据结构，在 dp 中咱们通常应用一维数组或者二维数据来存储，假如是 dp[]。

那么对应解 dp 问题咱们有以下过程

状态定义：确定 dp[] 中元素的含意，也就是说须要明确 dp[i] 是代表什么内容
状态转移：确定 dp[] 元素之间的关系，dp[i] 这个格子是由哪些 dp 格子推算而来的。如斐波那契数列中就有 dp[i] = dp[i – 1] + dp[i – 2]
起始值：base case，dp[] 中的哪些格子是能够间接得出后果的。如斐波那契数列中就有 dp[0] = 0 和 dp[1] = 1

咱们晓得应用「动静布局」的前提是问题的“无后效性”。

然而有些时候问题的“无后效性”并不容易体现。

须要咱们多引入一维来进行“打消”。

例如 LeetCode 上经典的「股票问题」，应用动静布局求解时往往须要多引入一维示意状态，有时候甚至须要再引入一维代表购买次数。

留神这里说的打消是带引号的，其实这样的做法更多的是作为一种“技巧”，它并没有真正扭转问题“后效性”，只是让问题看上去变得简略的。

到这里咱们曾经能够简略答复「动静布局」和「记忆化搜寻」的区别是什么了。

「记忆化搜寻」实质是带“缓存”性能的「暴力递归」：

它只能解决反复计算的问题，而不能确定两头后果的拜访机会和拜访次数，实质是一种“自顶向下”的解决形式；

「动静布局」是一种“自底向上”的解决方案：

能明确拜访机会和拜访次数，这为升高算法的空间复杂度带来微小空间，咱们能够依据依赖关系来决定保留哪些两头后果，而无须将全副两头后果进行“缓存”。

你好，我是三叶，算法爱好者，服役 OIer。

欢送点击下方名片关注我，咱们下次再见 🍭🍭🍭

宫水三叶的刷题日记

算法爱好者，服役 OIer，现微软工程师。「刷穿 LeetCode」系列文章原创公众号。

109 篇原创内容

公众号

关于算法-数据结构:浅谈动态规划

前言

演变过程

无后效性

1：暴力递归

2：记忆化搜寻

2.1：次优解版本的「记忆化搜寻」

3：从「自顶向下」到「自底向上」

动静布局的实质

打消“后效性”

总结

最初