通过仅相乘乘积≤k的相邻元素最小化数组元素个数

• 动态规划状态定义：设 dp[i] 代表数组前 i 个元素处理完成后的最小元素个数（建议将数组下标从1开始计数，方便状态推导）。
• 初始化规则：
  • dp[0] = 0（空数组的元素个数为0）
  • dp[1] = 1（单个元素无法合并，只能保留1个）
• 状态转移逻辑：
  对每个位置 i（从2遍历到数组总长度 n），从 i-1 开始倒序遍历 j：
  • 维护临时乘积 prod，初始值为当前元素 arr[i-1]（适配原数组0-based下标）
  • 将 arr[j-1] 乘入 prod，若 prod > k，直接终止当前j的遍历（因元素均为正数，继续往前乘只会让乘积更大，不可能满足<=k的条件）
  • 若 prod <= k，则更新 dp[i] = min(dp[i], dp[j-1] + 1)——含义是前 j-1 个元素的最优结果，加上合并 j 到 i 这一段的1个元素，取最小值
• 与矩阵链乘法（MCM）的核心差异：MCM允许任意矩阵链相乘，需遍历所有分割点；而本问题仅允许连续相邻元素合并，且有乘积上限，倒序遍历j时一旦乘积超标即可停止，无需遍历所有可能的分割点，逻辑更聚焦。
• 特殊情况预判：若数组中存在单个元素大于k，说明该元素无法与任何相邻元素合并，也无法单独满足条件（题目隐含所有元素<=k的前提，否则问题无解）。

内容的提问来源于stack exchange，提问作者ng.newbie