leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1105.cpp (595B)

      1 class Solution {
      2   public:
      3     int minHeightShelves(const vector<vector<int>> &books, int shelfWidth) const {
      4         static int dp[1001];
      5         memset(dp, 0x7F, sizeof(dp));
      6         const int n = books.size();
      7 
      8         dp[0] = 0;
      9         for (int i = 1; i <= n; i++) {
     10             int left = shelfWidth, height = 0;
     11             for (int j = i; j > 0 && books[j - 1][0] <= left; j--) {
     12                 left -= books[j - 1][0];
     13                 height = max(height, books[j - 1][1]);
     14                 dp[i] = min(dp[i], dp[j - 1] + height);
     15             }
     16         }
     17         return dp[n];
     18     }
     19 };