leetcode

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 };