Report: Triangle Min Path Sum

九章算法的学习DP的经典例子

题目

思路

问题

first trial : TLE

  • 如果使用简单的recursion会出现TLE, 代码如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    public class Solution {
        /**
         * @param triangle: a list of lists of integers.
         * @return: An integer, minimum path sum.
         */

        public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
            // write your code here
            int[] min = new int[]{Integer.MAX_VALUE};
            dfs(0, 0, 0, min, triangle);
            return min[0];
        }


        public static void dfs(int x, int y, int sum, int[] min, ArrayList<ArrayList<Integer>> triangle) {
            if (x == triangle.size()) {
                min[0] = Math.min(min[0], sum);
                return;
            }
            dfs(x+1, y, sum+triangle.get(x).get(y), min, triangle);
            dfs(x+1, y+1, sum+triangle.get(x).get(y), min, triangle);
            return;
        }
    }
    • Lintcode里面TLE的页面如下: TLE_lintcode
    • 有几个要注意的地方:
      1. 因为Lintcode是给了class, 要求写method. 虽然可以有helper method, 例如这里的dfs. 但是因为triangle不是field, 只是一个param, 所以必须要传给helper当param. 不然用不了.
      2. Lintcode 的 test case是看不到全部的… 所以也不能copy放到eclipse里面算了. 但是有个基本常识就是一般不能有超过20层的recursion. 所以尽量不用recursion才行.

2nd trial: pass

  • 看到这种Divide and Conquer的问题自然想到使用DP解决. 这样可以使用重复计算的部分, 而且避免递归. 注意到: 这是一个找min的值的问题. 自然是DP

Comments

▲ <<<<<<< Updated upstream ======= >>>>>>> Stashed changes <<<<<<< Updated upstream ======= >>>>>>> Stashed changes