线性动态规划：计算二进制字符串中连续1的子数组个数

题目描述

给你一个二进制字符串 s（只包含字符 '0' 和 '1'）。请计算并返回该字符串中 仅包含连续 '1' 的子数组 的个数。

注意：

• 子数组必须是原字符串中 连续 的一段。
• 子数组内必须 全部 是字符 '1'，不能包含任何 '0'。
• 即使两个子数组由相同的字符 '1' 组成，只要它们的 起始位置或结束位置不同，就视为不同的子数组。

示例 1：

输入：s = "0110111"
输出：9
解释：仅包含连续1的子数组如下（括号内为子数组在原字符串中的起始和结束索引）：
(1, 1) -> "1"
(1, 1) 是长度为1的子数组
(4, 4) -> "1"
(4, 4) 是长度为1的子数组
(5, 5) -> "1"
(5, 5) 是长度为1的子数组
(5, 6) -> "11"
(5, 6) 是长度为2的子数组
(4, 6) -> "111"
(4, 6) 是长度为3的子数组
(1, 1) 对应索引1处的'1'，它单独是一个子数组。
长度为2的子数组 "11" 是索引5和6处的'1'组成的。
长度为3的子数组 "111" 是索引4、5、6处的'1'组成的。
注意，索引0处的字符是'0'，所以不以它开头的子数组都不算。
总共：1（索引1）+ 1（索引4）+ 1（索引5）+ 2（索引5,6的"11"）+ 4（索引4,5,6的"111"）= 9 个子数组？
这里计算有误。我们重新统计：
从索引1开始的连续1子数组：(1,1) -> 1个
从索引4开始的连续1子数组：
  长度为1: (4,4)
  长度为2: (4,5) 但索引5是'1'，但注意字符串s="0110111"，索引4='1', 索引5='1', 索引6='1'，所以(4,5)是"11"，索引4开始的连续1直到索引6，所以有：
    从索引4开始，长度1: (4,4)
    长度2: (4,5)
    长度3: (4,6) -> 3个子数组
从索引5开始的连续1子数组：
  长度1: (5,5)
  长度2: (5,6) -> 2个子数组
从索引6开始的连续1子数组：
  长度1: (6,6) -> 1个子数组
总共: 1 + 3 + 2 + 1 = 7？ 但答案是9，说明我们漏了一些。
实际上，我们需要考虑所有可能的连续1片段，并对每个片段，计算其包含的子数组数。
字符串s = "0110111"
索引: 0 1 2 3 4 5 6
字符: 0 1 1 0 1 1 1
连续1的片段有：
片段A: 索引1~2，长度L1=2
片段B: 索引4~6，长度L2=3
对于一个长度为L的连续1片段，它包含的仅包含1的子数组的个数为 L*(L+1)/2。
因为从片段中任选一个开始位置i和结束位置j（i<=j，且都在片段内），都对应一个全1子数组。
所以片段A贡献：2*3/2=3
片段B贡献：3*4/2=6
总共：3+6=9
所以正确答案是9。

示例 2：

输入：s = "101"
输出：2
解释：仅包含连续1的子数组为：(0,0) -> "1" 和 (2,2) -> "1"。
注意(1,1)是'0'，不算。

示例 3：

输入：s = "1111"
输出：10
解释：整个字符串是连续的'1'，长度为4。包含的全1子数组个数为 4*5/2=10。

题目理解

我们需要找出字符串中所有由连续'1'组成的子数组的个数。一个由连续'1'组成的片段（即一段连续的'1'，两端可能是边界或'0'），其长度为L，那么这个片段内能形成的全1子数组的个数就是1+2+...+L = L*(L+1)/2。所以，我们只需要遍历字符串，识别出每一段连续'1'的片段，计算其长度L，然后累加L*(L+1)/2即可。

但题目要求用线性动态规划来解决。我们可以定义状态，用一次遍历完成计算。

动态规划解法

步骤一：定义状态
设 dp[i] 表示以字符串第 i 个字符（索引从0开始）结尾的、仅包含连续'1'的子数组的个数。

为什么这么定义？

• 如果s[i]是'0'，那么以它结尾的全1子数组个数为0，因为没有以'0'结尾的全1子数组。
• 如果s[i]是'1'，那么以它结尾的全1子数组可以：
  1. 只包含它自己（长度为1的子数组）。
  2. 如果前面是连续的'1'，那么可以接在前面形成的全1子数组后面，形成更长的子数组。

步骤二：状态转移方程
遍历 i 从 0 到 n-1（n为字符串长度）：

• 如果 s[i] == '0'：
  dp[i] = 0
• 如果 s[i] == '1'：
  • 如果 i == 0，前面没有字符，则只有它自己：dp[0] = 1
  • 否则，dp[i] = dp[i-1] + 1
    解释：以s[i]结尾的全1子数组个数 = 以s[i-1]结尾的全1子数组每个后面再加上s[i]（有dp[i-1]个） + 只包含s[i]自己的那1个。

步骤三：计算答案
最终答案就是所有 dp[i] 的和。因为dp[i]表示以位置i结尾的全1子数组个数，对所有的i求和，就得到了所有可能的全1子数组的个数。

步骤四：举例验证
以 s = "0110111" 为例，索引从0开始：

索引: 0 1 2 3 4 5 6
字符: 0 1 1 0 1 1 1
dp:   0 1 2 0 1 2 3
总和: 0+1+2+0+1+2+3 = 9

结果正确。

代码实现（Python）

def countSubstrings(s: str) -> int:
    n = len(s)
    dp = [0] * n
    total = 0
    for i, ch in enumerate(s):
        if ch == '1':
            if i == 0:
                dp[i] = 1
            else:
                dp[i] = dp[i-1] + 1
        else:
            dp[i] = 0
        total += dp[i]
    return total

空间优化：
因为 dp[i] 只依赖于 dp[i-1]，我们可以只用一个变量来记录前一个状态，将空间复杂度从O(n)降到O(1)。

def countSubstrings(s: str) -> int:
    cur = 0  # 当前以字符结尾的全1子数组个数
    total = 0
    for ch in s:
        if ch == '1':
            cur = cur + 1
        else:
            cur = 0
        total += cur
    return total

时间复杂度：O(n)，只需要一次遍历。
空间复杂度：O(1)。

思考扩展

这个问题是“统计全1子数组”的经典入门题。它可以很容易地扩展到更复杂的情况，比如：

1. 如果字符串是二维的（矩阵），统计全1子矩阵的个数。
2. 如果允许最多将k个'0'变成'1'，求最长的连续1的子数组长度（滑动窗口解法）。

但在本问题中，我们专注于最简单的情况，用线性动态规划来求解。通过定义dp[i]，我们能够以递推的方式计算出每个位置结尾的全1子数组个数，从而得到总数。