C语言重构【1105】填充书架

梦里梦外; 2022-11-06 07:00 135阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

附近的家居城促销，你买回了一直心仪的可调节书架，打算把自己的书都整理到新的书架上。
    
    你把要摆放的书 books 都整理好，叠成一摞：从上往下，第 i 本书的厚度为 books[i][0]，高度为 books[i][1]。
    
    按顺序 将这些书摆放到总宽度为 shelf_width 的书架上。
    
    先选几本书放在书架上（它们的厚度之和小于等于书架的宽度 shelf_width），然后再建一层书架。重复这个过程，直到把所有的书都放在书架上。
    
    需要注意的是，在上述过程的每个步骤中，摆放书的顺序与你整理好的顺序相同。 例如，如果这里有 5 本书，那么可能的一种摆放情况是：第一和第二本书放在第一层书架上，第三本书放在第二层书架上，第四和第五本书放在最后一层书架上。
    
    每一层所摆放的书的最大高度就是这一层书架的层高，书架整体的高度为各层高之和。
    
    以这种方式布置书架，返回书架整体可能的最小高度。
    
    示例：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_size_16_color_FFFFFF_t_70]

输入：books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelf_width = 4
    输出：6
    解释：
    3 层书架的高度和为 1 + 3 + 2 = 6 。
    第 2 本书不必放在第一层书架上。
     
    
    提示：
    1 <= books.length <= 1000
    1 <= books[i][0] <= shelf_width <= 1000
    1 <= books[i][1] <= 1000

#### 方案： ####

*  思想就是dp，dp数组的含义是前n本书的最小高度，假设每进来一本就新建一层，然后根据这个和之前的进行合并，
    
     *  可能会有朋友想到那些容量够的情况怎么办，也要合并吗？对此，我尝试过有容量就直接插入的方式，发现会漏掉某种情况，比如这组：
        
         *  `{152, 92}, {22, 133}, {91, 60}, {80, 120} shelf_width=200`如果容量足够就放入的话就会是：\{152, 92\}, \{22, 133\}和\{91, 60\}, \{80, 120\}两组，则高度为133+120，比最优解92+133要大一点，这个例子是很后面的例子，调了好久才发现这个错误。。。
         *  不过话又说回来，即使是全部都检查合并，速度依旧是100%。。。
         *  ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_size_16_color_FFFFFF_t_70 1]

class Solution
    { 
    public:
        int minHeightShelves(vector<vector<int>> &books, int shelf_width)
        { 
            int len = books.size();
            vector<int> dp(len, INT_MAX);
            //记录当前层剩余容量
            int tmp = shelf_width - books[0][0];
            //记录当前合并层的最高书
            int highest = books[0][1];
            //记录当前合并层最早的书的index
            int index = 0;
            dp[0] = books[0][1];
            for (int i = 1; i < len; i++)
            { 
                //本层的最高高度
                int now_hightest = books[i][1];
                //防止进不了循环的情况发生，此时就单单开新一行，然后放当前的就行了
                highest = now_hightest;
                //新增一层
                tmp = shelf_width - books[i][0];
                dp[i] = dp[i - 1] + now_hightest;
                int now_tmp = tmp;
                for (int j = i - 1; j >= 0 && now_tmp - books[j][0] >= 0; j--)
                { 
                    //计算当前层的高度，上一层剩余高度(dp[i-j])
                    now_hightest = max(now_hightest, books[j][1]);
                    now_tmp -= books[j][0];
                    //这里有点代码冗余，纯粹是为了j==0这个情况。。
                    if (j == 0 && dp[i] > now_hightest)
                    { 
                        tmp = now_tmp;
                        dp[i] = now_hightest;
                        highest = now_hightest;
                    }
                    else if (dp[i] > dp[j - 1] + now_hightest)
                    { 
                        tmp = now_tmp;
                        dp[i] = dp[j - 1] + now_hightest;
                        highest = now_hightest;
                    }
                }
            }
            return dp[len - 1];
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n2)
 *  空间复杂度：O(n)

[Git]: https://github.com/ch98road/leetcode
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_size_16_color_FFFFFF_t_70]: /images/20221023/268ce2c041bd483b8c8c22b7b686caef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_size_16_color_FFFFFF_t_70 1]: /images/20221023/744e95980196457ab047bd3b2ac34dcd.png