C++ O(N) space solution


  • 0
    C
    class Solution {
    public:
    /**method one dp O(N^2) time and space**//*
        int minimumTotal(vector<vector<int>>& t) {
            int ts = t.size();
            vector<vector<int>> dp(ts,vector<int>(ts,0));
            for(int j=0;j<ts;++j)
                dp[ts-1][j] = t[ts-1][j];
            for(int i=ts-2;i>=0;--i){
                for(int j=i;j>=0;--j){
                    dp[i][j] = t[i][j]+min(dp[i+1][j],dp[i+1][j+1]);
                }
            }
            return dp[0][0];
            
        }
    */
    /**method two dp O(N) space complexity**/
        int minimumTotal(vector<vector<int>>& t) {
            int ts = t.size();
            vector<vector<int>> dp(2,vector<int>(ts,0));
            for(int j=0;j<ts;++j)
                dp[0][j] = t[ts-1][j];
            int cur = 1,old = 0;
            for(int i=ts-2;i>=0;--i){
                for(int j=i;j>=0;--j){
                    dp[cur][j] = t[i][j]+min(dp[old][j],dp[old][j+1]);
                }
                swap(cur,old);
                
            }
            return dp[old][0];
            
        }
    };
    

Log in to reply
 

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