植物种植位置算法时间复杂度验证及最小成本求解咨询

问题背景 #

需要为有n个位置的花园种植m种花卉，相邻位置不能种植同种花卉，求覆盖所有位置的最小种植总成本。函数positioningPlants接收n*m的二维数组costs，costs[i][j]代表在位置i种植花卉j的成本，返回满足要求的最小总成本。

比如输入costs = [[4, 3, 7], [6, 1, 9], [2, 5, 3]]，位置1（索引1）种植花卉0的成本为6美元，种植花卉2的成本为9美元。

你的理解与实现代码 #

你认为该解决方案的时间复杂度为O(row * column * column)，原因是嵌套循环中包含Math.min()和array.slice()操作，实现代码如下：

const positioningPlants = (costs) => {
  const array = costs.map(cost => cost.map(c => c));

  for (let i = 1; i < costs.length; i++) {
    for (let j = 0; j < costs[0].length; j++) {
      const firstMin = Math.min(...array[i - 1].slice(0, j));
      const secondMin = Math.min(...array[i - 1].slice(j + 1));

      array[i][j] += Math.min(firstMin, secondMin);
    }
  }

  return Math.min(...array[array.length - 1]);
};

时间复杂度验证 #

你的判断是正确的，该方案时间复杂度确实为O(row * column²)：

• 外层循环执行row次（对应n个位置）
• 内层循环每个column（对应m种花卉），都要执行两次slice和Math.min操作：
  • array.slice(0,j)和array.slice(j+1)的时间复杂度为O(column)，因为需要复制对应长度的子数组
  • 展开子数组调用Math.min(...)的时间复杂度也为O(column)，因为要遍历子数组所有元素找最小值
• 每个内层循环迭代的总操作量为O(column)，因此整体时间复杂度为row * column * column = O(nm²)

方案合理性分析 #

这个动态规划的思路是正确的：

• 核心逻辑用array[i][j]记录位置i种植花卉j时的最小累计成本，等于当前种植成本加上前一个位置不种植j的最小成本
• 最终取最后一行的最小值，就是覆盖所有位置的最小总成本，完全符合问题要求

不过当前实现有优化空间：每次找前一行排除j的最小值时，都要切分数组再计算，效率较低。可以提前遍历前一行，找出最小值、次小值以及最小值对应的索引：

• 如果当前j不是最小值的索引，直接用最小值
• 如果当前j是最小值的索引，就用次小值
  这样可以把时间复杂度降到O(row * column)，大幅提升性能，尤其是当花卉种类（column）较多时。

内容的提问来源于stack exchange，提问作者Tui