leetcode

Solution to some Leetcode problems written in C++

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

1105.cpp (595B)

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