Leetcode problem 'Triangle' can be solved using DFS


  • 0
    T

    For the problem in http://oj.leetcode.com/problems/triangle/
    I think it can be solved using DFS

    let's use T[i][j] to represent the triangle

    some pseudo code is like:

    int min_sum = MIN_INT;
    void findMinPath(int i, int j, int sum){
        if(i>n){
            min_sum = sum < min_sum ? sum : min_sum;
        } else {
            sum =+ T[i][j];
        }
        findMinPath(i+1, j, sum);
        findMinPath(i+1, j+1, sum);
    }
    

    min_sum is the result
    time complexity: O(n^2)
    space complexity: O(1) if you don't count stack; O(n) if you count stack

    Can you please let me know if you think this doesn't work?
    Thank you for any comments


  • 0
    T

    did you pass the test?
    Generally speaking, if you can pas the test, the code is ok.


  • -2
    J

    With some fixing up I think your code would work (not sure it would pass the judge time wise).

    You should aim for an O(n) solution though:

    int minimumTotal(vector<vector<int> > &triangle) {
        for (int i = triangle.size() - 1; i > 0; --i) {
            for (int j = 0; j < i; j++) {
                if (triangle[i][j] < triangle[i][j+1])
                    triangle[i-1][j] += triangle[i][j];
                else
                    triangle[i-1][j] += triangle[i][j+1];
            }
        }
        return triangle[0][0];
    }
    

    The idea is to start from the bottom row and work your way up the triangle. For every two adjacent elements choose the smallest and add it to the element above it.


  • 0
    B

    DFS is my first though too. Now that you've implemented it, you can try to get the bonus points.


  • 0
    S

    respect for the trying for constant extra space man! but it is kind of risky for modifying the original data structure


  • 4
    E

    Looks like if you are using top down, you will be adding all the node values to the sum.

    In my solution I use bottom up rather than top down.

    public class Solution {
        public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
            if (triangle == null || triangle.size() == 0) return 0;
            
            int length = triangle.size();
            int[] cLine = new int[length];
            
            //Initial value is the last line
            ArrayList<Integer> lastLine = triangle.get(length - 1);
            for (int j = 0; j < length; j++) {
                cLine[j] = lastLine.get(j);
            }
            
            //Updating from bottom up
            for (int i = length - 2; i >= 0; i--) {
                ArrayList<Integer> line = triangle.get(i);
                for (int j = 0; j < i + 1; j++) {
                    cLine[j] = line.get(j) + Math.min(cLine[j], cLine[j+1]);
                }
            }
            return cLine[0];
        }
    }

  • 1
    D

    It won't work. It is of complexity O(2^n) where n is the number of lines in triangle. It will fail with TLE.
    See how many times each node is visited:
    1
    121
    1331
    14641
    ...
    and total number of visits each level: 1, 4, 8, 16 .... I wrote a test case with 15 lines your solution should have called the recursive call 32767 times.


  • 0
    P

    My initial DFS solution failed due to TLE, so I think the author's answer should not get accepted...


  • 0
    C

    Nice -- this is the most elegant solution I have seen.


  • 0
    Y

    I guess min_sum should be initialized to be MAX_INT, right?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.