Leetcode problem 'Triangle' can be solved using DFS

Question

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

Answer 1

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

Answer 2

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

Answer 3

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];
    }
}

Answer 4

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.

Comments

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