题目描述

给定一个定长停车场，用整型字符串数组$cars$表示车位占用情况，其中$1$表示有车，$0$表示空位。车辆有三种尺寸：小车占据长度$1$，货车占据长度$2$，卡车占据长度$3$。请统计在当前停放状况下，停车场最少可以停多少辆车，并返回该最小车数。

思路

1. 将数组拆分为若干段连续的“有车区间”，每个区间长度记为$L$。
2. 对于每个长度为$L$的区间，要用尺寸为$3,2,1$ 的车来覆盖，使得车辆总数最少。
3. 这是一个经典的“凑零钱”最少硬币问题，面值为$3,2,1$，对于此面值体系，贪心算法（优先使用最大面值）可得到最优解。

题目描述

特定大小的停车场，数组 $cars$[]表示，其中 $1$ 表示有车， $0$表示没车。车辆大小不一，小车占一个车位(长度 $1$ )，货车占两个车位(长度 $2$)，卡车占三个车位(长度 $3$)，统计停车场最少可以停多少辆车，返回具体的数目。

输入描述

整型字符串数组 $cars$，其中 $1$ 表示有车，$0$ 表示没车，数组长度小于 $1000$。

输出描述

整型数字字符串，表示最少停车数目。

样例1

输入

1,0,1

输出

2

说明：$1$ 个小车占第 $1$ 个车位，第二个车位空，$1$ 个小车占第 $3$ 个车位最少有两辆车。

样例2

输入

1,1,0,0,1,1,1,0,1

输出

3

说明：$1$ 个货车占第 $1$、 $2$ 个车位，第 $3$ 、$4$ 个车位空

​ $1$ 个卡车占第 $5$ 、$6$ 、$7$ 个车位

​ 第 $8$ 个车位空

​ $1$ 个小车占第 $9$ 个车位最少 $3$ 辆车