Share my C++ 5 lines DP and O(1) space DFS passed 42/43, any ideas?


  • 0

    DP 5 lines bottom-up

        int minimumTotal(vector<vector<int>>& triangle) {
            vector<int>dp=*(triangle.end()-1);
            for(int i=triangle.size()-2;i>=0;i--)
                for(int j=0;j<=i;j++)
                    dp[j]=min(dp[j],dp[j+1])+triangle[i][j];
            return dp[0];
        }
    

    Initially, I thought it's a traversal problem, wrote the O(1) space DFS solution below, but got TLE on the last TC, well, If all numbers are positive, it will be a backtracking problem and DFS could work, but since it contains negative number and each path has to be checked, don't know how to improve it.
    Is it possible for DFS solution to get accepted?

        int minimumTotal(vector<vector<int>>& triangle) {
            int minSum=INT_MAX;
            DFS(triangle,triangle[0][0],1,0,minSum);
            return minSum;
        }
        
        void DFS(vector<vector<int>>& triangle,int sum,int level,int index,int& minSum){
            if(level==triangle.size()){
                minSum=min(minSum,sum);
                return;
            }
            sum+=triangle[level][index];
            DFS(triangle,sum,level+1,index,minSum);
            sum-=triangle[level][index];
            sum+=triangle[level][index+1];
            DFS(triangle,sum,level+1,index+1,minSum);
        }
    

Log in to reply
 

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