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