leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

2742.cpp (1888B)

0 // Top-down 1 class Solution { 2 static int dp[501][501]; 3 4 public: 5 Solution() { memset(dp, 0xFF, sizeof(dp)); } 6 int paintWalls(const vector<int> &cost, const vector<int> &time, int crnt = 0, int total = 0) { 7 if (total >= cost.size()) return 0; 8 if (crnt == cost.size()) return 1e9; 9 if (dp[crnt][total] != -1) return dp[crnt][total]; 10 11 const int paint = cost[crnt] + paintWalls(cost, time, crnt + 1, total + time[crnt] + 1); 12 const int dont = paintWalls(cost, time, crnt + 1, total); 13 return dp[crnt][total] = min(paint, dont); 14 } 15 }; 16 17 int Solution::dp[501][501]; 18 19 // Bottom-up 20 class Solution { 21 public: 22 int paintWalls(const vector<int> &cost, const vector<int> &time) { 23 static unsigned dp[501][501]; 24 memset(dp, 0x00, sizeof(dp)); 25 26 const int n = cost.size(); 27 for (int i = 1; i <= 500; i++) 28 dp[n][i] = 1e9; 29 30 for (int i = n - 1; i >= 0; i--) { 31 for (int remain = 1; remain <= n; remain++) { 32 const int paint = cost[i] + dp[i + 1][max(0, remain - time[i] - 1)]; 33 const int dont = dp[i + 1][remain]; 34 dp[i][remain] = min(paint, dont); 35 } 36 } 37 38 return dp[0][n]; 39 } 40 }; 41 42 // Space optimized Bottom-up 43 class Solution { 44 public: 45 int paintWalls(const vector<int> &cost, const vector<int> &time) { 46 static unsigned dp[501], pdp[501]; 47 48 const int n = cost.size(); 49 for (int i = 1; i <= 500; i++) 50 pdp[i] = 1e9; 51 52 for (int i = n - 1; i >= 0; i--) { 53 for (int remain = 1; remain <= n; remain++) { 54 const int paint = cost[i] + pdp[max(0, remain - time[i] - 1)]; 55 const int dont = pdp[remain]; 56 dp[remain] = min(paint, dont); 57 } 58 swap(dp, pdp); 59 } 60 61 return pdp[n]; 62 } 63 };