Another C++ DP with a technique for switching between the two DP rows


  • 0
    M

    It seems like some DP problems start off with an M x N table that can then be reduced to a 2 by N table and the code juggles writing over the previously used row. I've found that a C++ lambda that computes (row % 2) for the row index can help isolate the row-switching logic:

            int minCost(vector<vector<int>>& costs)
            {
                auto N = static_cast<int>(costs.size());
    
                // DP table is two rows.
                int T[2][3] = { 0 };
    
                // Alternates between the two DP rows
                auto dp = [&](int row)
                { return T[row & 1]; };
    
                for (int i = 0; i < N; ++i)
                {
                    dp(i + 1)[0] = costs[i][0] + min(dp(i)[1], dp(i)[2]);
                    dp(i + 1)[1] = costs[i][1] + min(dp(i)[0], dp(i)[2]);
                    dp(i + 1)[2] = costs[i][2] + min(dp(i)[1], dp(i)[0]);
                }
    
                auto best = min({ dp(N)[0], dp(N)[1], dp(N)[2] });
                return best;
            }
    

Log in to reply
 

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