从暴力递归走向动态规划——研究过卡特兰数的同学欢迎进来


本人最近刷了一些的dp的题目。其中一些题目,它们拥有相似甚至相同的算法框架,其思路都是利用卡特兰数的性质来解决。本人稍微总结了一下一些经验,希望帮助大家更高效的刷题,并少走弯路。如果你有更好的解法,欢迎进行探讨。

卡特兰数的定义

卡特兰数又称卡塔兰数,英文名Catalan number,是组合数学中一个常出现在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名,其前几项为 : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790......
其递推公式为:
f(n)= f(0)*f(n-1)+f(1)*f(n-2)+...+f(n-1)*f(0) (n>=2)
例如:f(2)=f(0)*f(1)+f(1)*f(0)=1*1+1*1=2
f(3)=f(0)*f(2)+f(1)*f(1)+f(2)*f(0)=1*2+1*1+2*1=5

卡特兰数的应用

1、 n对括号正确匹配数目
给定n对括号,求括号正确配对的字符串数,例如:
0对括号:[空序列] 1种可能
1对括号:() 1种可能
2对括号:()() (()) 2种可能
3对括号:((())) ()(()) ()()() (())() (()()) 5种可能

2、凸多边形的三角划分
在一个凸多边形中,通过若干条互不相交的对角线,把这个多边形划分成了若干个三角形。任务是输入凸多边形的边数n,输出不同划分的方案数f(n)
n=0,1,2,均不能组成多边形,故而f(0)=f(1)=f(2)=0
n=3, 本身就是三角形,无需划分,故而f(3)=1
n=4, 考虑矩形,正反对角线,显然f(4)=2
n=5,五边形,一共五种,f(5)=5,如下图所示:
请输入图片名称
n=6, 六边形,一共14种,f(6)=14,如下图所示:
请输入图片名称

3、给定节点组成二叉搜索树
给定N个节点,能构成多少种不同的二叉搜索树?
n=0,规定空树也是一颗BST,故f(0)=1
n=1,显然f(1)=1
n=2,f(2)=2,如下图所示:
请输入图片名称
n=3,f(3)=5,如下图所示:
请输入图片名称
另外还有出栈顺序,排队找零问题等等,有兴趣的同学可以查阅相关资料

基本例题

leetcode 96. Unique Binary Search Trees
请输入图片名称
显然,此题就是上文中所提到的第三个应用。下面,我们就尝试着用不同的算法来解决这道题。

1、暴力搜索法
仿照斐波那契数列,定义如下递归式:
请输入图片名称
所以第一种算法就有了:
public int numTrees(int n) {
            if(n<=1){
                return 1;
            }else{
                int sum=0;
                for(int i=0;i<=n-1;i++){
                    sum+=numTrees(i)*numTrees(n-1-i);
                }
                return sum;
            }
        }


乍一看没什么问题,但是,当n>=18时,就TLE了!
请输入图片名称
为什么会TLE呢?我们不妨看一下当n=4时候的递归树:
请输入图片名称
可见,f(2)调用了2次,f(0)与f(1)更是重复调用了多次,当n更大的时候,重复计算的节点会更多。由于每个非叶子节点至少可以分成更小的两个子节点,所以整个算法的时间复杂度超过O(2^N),是指数级别的,必定TLE。

2、记忆搜索法
可以开一个数组,当某个节点递归完成的时候,就把结果记录到数组中。这样,下次递归这个子节点的时候就无需再重复计算该子节点及其孙子节点、重孙子节点了,直接返回该子节点下标所对应的值即可,不妨把这个数组叫做dp

class Solution {
    public int numTrees(int n) {
            if(n<=1){
                return 1;
            }else{
                int[] dp=new int[n+1];
                dp[0]=dp[1]=1;
                return dfs(n, dp);
            }
        }
     private int dfs(int n,int[] dp){
         if(dp[n]!=0){
             return dp[n];
         }else{
             int sum=0;
             for(int i=0;i<=n-1;i++){
                 sum+=dfs(i, dp)*dfs(n-1-i, dp);
             }
             return dp[n]=sum;
         }
     }
}

结果:Accepted!
3、动态规划法
还记得动态规划法的两个适用条件吗?
(1) 最优子结构
(2) 重叠子问题
先来看条件1,递归式本身就符合,而且是一个只包含加法和乘法的非常简单的最优子结构;再来看条件2,递归树中重复计算的节点,本身就等价于重叠子问题。
故而,自底向上的动态规划法诞生了,它的时间复杂为O(N^2),空间复杂度为O(N):

class Solution {
    public int numTrees(int n) {
        if (n <= 1) {
            return 1;
        }
        int[] dp = new int[n+1];
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int sum = 0;
            for (int j = 0; j <= i - 1; j++) {
                sum+= dp[j] * dp[i - 1 - j];
            }
            dp[i] = sum;
        }
        return dp[n];
    }
}

结果:Accepted!
4、状态压缩法
既然用数组能解决问题,那我们能否仿照“斐波那契数列三个变量来回换”的方法,优化一下空间复杂度呢?其实是可以的,但是需要借助于另外一个递推公式:
f(n)=f(n-1)*(4*n-2)/(n+1)
于是第三种算法就有了,它的时间复杂度为O(N),空间复杂度为O(1)

    public int numTrees(int n) {
        if (n <= 1) {
            return 1;
        }
        long a = 1;
        for (int i = 2; i <= n; i++) {
            // 防止溢出要用long
            long b = a * ((i << 2) - 2) / (i+1);
            a = b;
        }
        return (int) a;
    }

结果:Accepted!
其实,还可以借助于通项公式:f(n)=C(2n,n)/(n+1),这个通项公式,也很好的解释了暴力递归的时间复杂度。
有兴趣的同学,可以借助于通项公式完成另一个时间复杂度为O(N),空间复杂度为O(1)的算法。

矩阵连乘

问题描述:
给定n个矩阵{A1,A2,A3,...,An},其中Ai与Ai+1是可乘的,求这n个矩阵的最优计算次序,输出最少需要的乘法次数。
举例:A1=10*100,A2=100*5,A3=5*50
如果以(A1A2)A3的次序计算,总次数为:
10*100*5+10*5*50=7500
如果以A1(A2A3)的次序计算,总次数为:
100*5*50+10*100*50=75000
输出:7500
两者竟相差10倍,可见,矩阵的加括号(结合)顺序对连乘次数的影响巨大,那么,如何求出最优乘法次数呢?
不失一般性,假设需要计算子矩阵{Ai,Ai+1,Ai+2,...,Aj}的最优连乘次数,其中0<=i<=j<n-1。
那么,在进行最后一次相乘的时候,矩阵必定是从某个位置断开,假设这个位置为k,那么矩阵数组被k分割成两个更小的子矩阵:
(Ai,Ai+1,...,Ak)(Ak+1,Ak+2,...,Aj)
似乎,只要求出子矩阵(Ai,Ai+1,...,Ak)以及(Ak+1,Ak+2,...,Aj)各自的最优连乘次数,并加上这两个子矩阵的最后一次相乘的次数,就是整个矩阵{Ai,Ai+1,Ai+2,...,Aj}的最优连乘次数。于是,我们得到了一个递归式:
dp[i][j]=min{dp[i][k]+dp[k+1][j]+Row[i]*Col[k]*Col[j]},其中,i<=k<j,
Row表示矩阵的行数,Col表示矩阵的列数
那么,这个递归式是否正确呢?我们不妨用反证法来证明:
假设总问题dp[i][j]是最优解,且k是最优解断开矩阵的下标元素,但子问题dp[i][k]或子问题dp[k+1][j]不是最优解,于是,我们可以找到子问题的另外两个更优解dp'[i][k]与dp'[k+1][j],使得
(dp'[i][j]=dp'[i][k]+dp'[k+1][j]+Row[i]*Col[k]*Col[j])<=(dp[i][j]=dp[i][k]+dp[k+1][j]+Row[i]*Col[k]*Col[j])
与原假设“总问题dp[i][j]是最优解”相矛盾,故而子问题dp[i][k]和子问题dp[k+1][j]必然是最优解。
自此,我们证明了矩阵连乘问题符合最优子结构性质
1、暴力递归法
其实有以上的最优子结构性质,我们就可以写出最原始的暴力递归算法。
假设用二维数组来表示需要相乘的n个矩阵,matrixArray = {{30, 35}, {35, 15}, {15, 5}, {5, 10}, {10, 20},{20, 25}};

public class MatrixChain {
    public static final int MAX = 6553500;
    //这里的callCnt是为了表示调用次数
    public int callCnt = 0;
    public int bruteForce(final int[][] matrixArray, int i, int j) {
        callCnt++;
        if (i == j) {
            return 0;
        } else if (j - i == 1) {
            return matrixArray[i][0] * matrixArray[i][1] * matrixArray[j][1];
        } else {
            int min = MAX;
            for (int k = i; k < j; k++) {
                min = Math.min(
                        min,
                        bruteForce(matrixArray, i, k)
                                 +bruteForce(matrixArray, k+1, j)
                                 +matrixArray[i][0] * matrixArray[k][1]
                                * matrixArray[j][1]);
            }
            return min;
        }
    }
    public static void main(String[] args) {
        MatrixChain solution = new MatrixChain();
        int[][] matrixArray = {{30, 35}, {35, 15}, {15, 5}, {5, 10}, {10, 20},
                {20, 25}};
        System.out.println(solution.bruteForce(matrixArray, 0,
                matrixArray.length - 1));
        System.out.println(solution.callCnt);
    }
}

输出:
15125
135
可见,虽然只有6个矩阵,但是函数一共调用了135次,初步分析来看,算法的时间复杂度还是比较大的,为什么出现成这种现象?
2、记忆搜索法
我们不妨分析一下,求{A2A3A4A5}时候的递归树:
请输入图片名称
可见,A2A3、A3A4、A4A5,均被重复调用了,所以我们可以用一个二维数组来缓存已经计算过的值来防止函数的重复调用,于是有了第二种解法:

public class MatrixChain {
    public static final int MAX = 6553500;
    public int callCnt = 0;
    private int dfs(final int[][] matrixArray, int[][] dp, int i, int j) {
        callCnt++;
        if (dp[i][j] != MAX) {
            return dp[i][j];
        } else {
            if (i == j) {
                return dp[i][i] = 0;
            } else if (j - i == 1) {
                return dp[i][j] = matrixArray[i][0] * matrixArray[i][1]
                        * matrixArray[j][1];
            } else {
                int min = MAX;
                for (int k = i; k < j; k++) {
                    min = Math.min(
                            min,
                            dfs(matrixArray, dp, i, k)
                                     +dfs(matrixArray, dp, k+1, j)
                                     +matrixArray[i][0] * matrixArray[k][1]
                                    * matrixArray[j][1]);
                }
                return dp[i][j] = min;
            }
        }
    }
    public int searchWithDp(final int[][] matrixArray) {
        int n = matrixArray.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = MAX;
            }
        }
        dfs(matrixArray, dp, 0, n - 1);
        return dp[0][n - 1];
    }
    public static void main(String[] args) {
        MatrixChain solution = new MatrixChain();
        int[][] matrixArray = {{30, 35}, {35, 15}, {15, 5}, {5, 10}, {10, 20},
                {20, 25}};
        System.out.println(solution.searchWithDp(matrixArray));
        System.out.println(solution.callCnt);
    }
}

输出:
15125
61
可见,作为缓存的dp数组为我们省去了不少重复计算。
3、动态规划法
既然我们在上文中确定了矩阵连乘的最优子结构,又通过分析递归树确定了它的重叠子问题,故而可以使用动态规划法来解决,接下来就要确定填矩阵的顺序了。到底用什么样的顺序来填写矩阵呢?我们还是要分析递归树,不妨采用自底向上的方式,随机取几个节点进行分析。
在计算长度为2的{A4A5}之前,长度为1的A4、A5必须先要计算出来
在计算长度为3的{A2A3A4}之前,长度为2的{A2A3}、{A3A4}以及长度为1的A2、A4必须先要计算出来
在计算长度为4的{A2A3A4A5}之前,长度为3的{A2A3A4}、{A3A4A5},长度为2的{A2A3}、{A4A5}以及长度为1的A5、A2必须先要计算出来
所以,填矩阵的过程,其实是子矩阵长度不断增加的过程,一开始是从左上到右下的对角线(长度为1),接下来是右上方一点的对角线(长度为2)......依次类推,最后是最右上角的点(长度为n)。用step表示步长,定义单个矩阵的步长为0,整个矩阵的步长为n-1,填写顺序如下图所示:
请输入图片名称
有了矩阵的填写顺序,动态规划算法就比较容易写出来了:

public class MatrixChain {

    public static final int MAX = 6553500;
    public int callCnt = 0;
    public int dpValue(final int[][] matrixArray) {
        int n = matrixArray.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = MAX;
            }
        }
        for (int i = 0; i < n; i++) {
            dp[i][i] = 0;
        }
        for (int i = 0; i < n - 1; i++) {
            dp[i][i+1] = matrixArray[i][0] * matrixArray[i][1]
                    * matrixArray[i+1][1];
        }
        for (int step = 2; step < n; step++) {
            for (int i = 0; i+step < n; i++) {
                int j = i+step;
                for (int k = i; k < j; k++) {
                    callCnt++;
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] +dp[k +1][j]
                            +matrixArray[i][0] * matrixArray[k][1]
                            * matrixArray[j][1]);
                }
            }
        }
        return dp[0][n - 1];
    }
    public static void main(String[] args) {
        MatrixChain solution = new MatrixChain();
        int[][] matrixArray = {{30, 35}, {35, 15}, {15, 5}, {5, 10}, {10, 20},
                {20, 25}};
        System.out.println(solution.dpValue(matrixArray));
        System.out.println(solution.callCnt);
    }
}

输出:
15125
30
又优化了不少,整个算法的时间复杂度、空间复杂度均为O(N^2),有兴趣的同学可以试试能否进行状态压缩。自此,我们已经成功利用动态规划法求出了问题的最优值。
4、构造最优解
有了自底向上求解最优值的动态规划,如何构造最优解就能迎刃而解了。在以上的动态规划算法中,可以加一个二维数组solution,用来记录每次断裂矩阵的位置,即记录k的位置。由于最优解也是自底向上构造的,所以可以编写一个递归函数来构造最优解,这个递归函数的框架和二叉树的后序遍历是完全一致的,不妨叫它postOrder,算法如下:

public class MatrixChain {
    public static final int MAX = 6553500;
    public void dpSolution(final int[][] matrixArray) {
        int n = matrixArray.length;
        int[][] dp = new int[n][n];
        int[][] solution = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = MAX;
            }
        }
        for (int i = 0; i < n; i++) {
            dp[i][i] = 0;
            solution[i][i] = i;
        }
        for (int i = 0; i < n - 1; i++) {
            dp[i][i +1] = matrixArray[i][0] * matrixArray[i][1]
                    * matrixArray[i+1][1];
            solution[i][i+1] = i;
        }
        for (int step = 2; step < n; step++) {
            for (int i = 0; i+step < n; i++) {
                int j = i +step;
                for (int k = i; k < j; k++) {
                    int t = dp[i][k]+dp[k +1][j]+matrixArray[i][0]
                            * matrixArray[k][1] * matrixArray[j][1];
                    if (t < dp[i][j]) {
                        dp[i][j] = t;
                        solution[i][j] = k;
                    }
                }
            }
        }
        System.out.println(dp[0][n - 1]);
        String result = postOrder("", solution, 0, n - 1);
        System.out.println(result.substring(1, result.length()));
    }
    private String postOrder(String str, final int[][] solution, int i, int j) {
        if (i == j) {
            return "A"+(i+1);
        } else if (j - i == 1) {
            return "(A" +(i+1)+"A"+(j+1)+")";
        } else {
            String left = postOrder(str, solution, i, solution[i][j]);
            String right = postOrder(str, solution, solution[i][j]+1, j);
            String result = "(" +left +right +")";
            return result;
        }
    }
    public static void main(String[] args) {
        MatrixChain_Original solution = new MatrixChain_Original();
        int[][] matrixArray = {{30, 35}, {35, 15}, {15, 5}, {5, 10}, {10, 20},
                {20, 25}};
        solution.dpSolution(matrixArray);
    }
}

输出:
15125
(A1(A2A3))((A4A5)A6))
由于每个产生局部最优解的位置k均只调用一次,故而postOrder函数的时间复杂度为O(N),所以整个算法的时间复杂任然是O(N^2)。自此,我们已经完全解决了矩阵连乘问题。
总结一下动态规划求解问题的步骤:
1、最优子结构:分析问题是否具有最优子结构,如果有,则写出递归式
2、暴力递归:如果有最优子结构,写出暴力递归算法并举例验证程序的正确性,如:在OJ系统中显示TLE
3、重叠子问题:其实有了暴力递归产生的TLE,事情就已经成功了一大半,这时候,画出递归树,看看是否有重复计算的节点
4、记忆搜索:在暴力递归算法中打一个表table,如数组、哈希表等,实现记忆搜索方法。其实对于大部分问题来说,如果OJ系统判题不是很严格,记忆搜索就已经能AC了
5、Table填充顺序:根据递归树的顺序,自底向上的确定表的填充顺序
6、计算最优值:根据第5步的表填充顺序,编写自底向上的动态规划算法,计算最优值
7、构造最优解:根据计算最优值时候得到的信息,构造问题的最优解。
8、状态压缩:如果有MLE,就检查程序是否能进行空间优化,利用滚动数组、临时变量等手段进一步缩小空间复杂度。
以上步骤,虽然有点笨,但是非常稳,对于不是很熟悉动态规划的同学而言,可以依照以上步骤来切dp的题。

24点游戏

算24是一个经典的游戏,恰好,leetcode上也有了这道题
leetcode 679. 24 Game
请输入图片名称
其实,不仅仅是4张牌算24,拓展到用n张牌去算任意数字m,都是同样的道理,我们就尝试着用矩阵连乘的思路来解决这道题。
利用数字8、4、7、1,怎样才能算出24呢?不妨只分析问题的最后一步,有三种情况:
(1)、8、4、7三个数字先结合,算出一系列的结果,假设为leftSet,然后leftSet中任意抽取一个数字和1进行某种四则运算,得到24
(2)、8、4与7、1两组数字分别结合,分别算出一系列的结果,假设为leftSet、rightSet,leftSet和rightSet中分别抽取两个数字进行某种四则运算,得到24
(2)、4、7、1三个数字先结合,算出一系列的结果,假设为rightSet,然后rightSet中任意抽取一个数字和8进行某种四则运算,得到24
以上是24点游戏最优子结构的定义
接下来分析重叠子问题,画出如下递归树,其中,?表示某种计算规则:
请输入图片名称
可以看到,47、71、84这三个节点均被重复计算了。所以,24点问题满足动态规划的最优子结构和重叠子问题双重特性。而且,它的填表方式和矩阵连乘是一模一样的,只是,算法不需要记录某个过程的max或者min,取而代之的,它需要记录每个结合的过程四则运算所产生的结果。还有,不要忘了,8、4、7、1是原数组4、1、8、7通过某种交换方式得到的排列,单单以4、1、8、7的顺序是无法计算24的,故而,我们的算法还需加上全排列,为了使整个算法都是非递归的,我们使用nextPermutation来实现全排列。以下是AC-Code:

import java.util.HashSet;
public class Solution {
    @SuppressWarnings("unchecked")
    public boolean judgePoint24(int[] nums) {
        for (int p = 1; p <= 24; p++) {
            HashSet<Double>[][] dp = new HashSet[nums.length][nums.length];
            for (int i = 0; i < nums.length; i++) {
                dp[i][i] = new HashSet<Double>();
                dp[i][i].add((double) nums[i]);
            }
            for (int step = 1; step < nums.length; step++) {
                for (int i = 0; i+step < nums.length; i++) {
                    HashSet<Double> set = new HashSet<Double>();
                    int j = i +step;
                    for (int k = i; k < j; k++) {
                        HashSet<Double> leftSet = dp[i][k];
                        HashSet<Double> rightSet = dp[k+1][j];
                        for (double left : leftSet) {
                            for (double right : rightSet) {
                                set.add(left+right);
                                set.add(left - right);
                                set.add(left * right);
                                if (right != 0) {
                                    set.add(left / right);
                                }
                            }
                        }
                    }
                    dp[i][j] = set;
                }
            }
            HashSet<Double> resultSet = dp[0][nums.length - 1];
            for (double d : resultSet) {
                if (Math.abs(d - 24) <= 0.00001) {
                    return true;
                }
            }
            nextPermutation(nums);
        }
        return false;
    }
    private void swap(int[] array, int a, int b) {
        int t = array[a];
        array[a] = array[b];
        array[b] = t;
    }
    private void reverse(int[] array, int from, int to) {
        while (from < to) {
            swap(array, from, to);
            from++;
            to--;
        }
    }
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int firstMax = n;
        for (int i = n - 1; i > 0; i--) {
            if (nums[i] > nums[i - 1]) {
                firstMax = i;
                break;
            }
        }
        if (firstMax == n) {
            reverse(nums, 0, n - 1);
            return;
        }
        int maxMinIndex = n - 1;
        while (maxMinIndex >= firstMax) {
            if (nums[maxMinIndex] > nums[firstMax - 1]) {
                break;
            }
            maxMinIndex--;
        }
        swap(nums, firstMax - 1, maxMinIndex);
        reverse(nums, firstMax, n - 1);
    }
}

你可以看到,外层for循环的step、i、j、k等变量完全都是矩阵连乘的套路!
其实,算法还有很大优化的空间和其它注意点,如:
(1)如何输出24点游戏的解?提示:可以利用逆波兰式
(2)通过8、4、7、1交换得到的另外一个排列7、1、8、4,其71、84两个子节点的值是完全一样的,只是所在排列的位置不同而已,如何避免不同的排列计算相同的子节点?
(3)如果使用搜索算法,由于数组只含有正整数1-9,我们还可以进行估价与剪枝,比如前三数字计算出的最大值为10,最后一个数字为2,那么,即使把10和2相乘也是小于24的,这种无效的分支可直接减去
(4)使用纯粹的暴力递归,依然是可以AC的,有兴趣的同学可以试一试
最后,我们总结一下卡特兰型dp的算法框架:

public Type dpSolution(Type[] array) {
        int n=array.length;
        //打表
        TableSet<Type> dp;
        //进行初始化操作
        init(dp);
        for (int step = 1; step < n; step++) {
            for (int i = 0; i+step < n; i++) {
                int j = i+step;
                for (int k = i; k < j; k++) {
                    //利用已经计算好的dp[i][j]、dp[k][j],通过递归式的定义f(n)计算最优值t
                    int t=f(dp[i][k],dp[k][j]);
                    //更新最优值
                    dp[i][j]=minOrMax(dp[i][j], t);
                }
            }
        }
        return dp[n];
    }

另外,最优BST、leetcode22、leetcode95、leetcode139、leetcode140、leetcode241等均可利用上述算法框架或卡特兰数的性质进行求解,有兴趣的同学可以试着AC它们。
已邀请:

要回复问题请先登录注册

返回顶部