优化动态规划代码的空间复杂度 - 使用滚动数组技巧

要优化以上代码的空间复杂度，可以考虑使用滚动数组的方法来减少空间的使用。\n\n滚动数组是一种空间优化的技巧，适用于状态转移方程中的状态只与前面的若干个状态有关的情况。在本题中，我们可以使用两个一维数组来表示二维数组dp，分别表示dp[i-1]和dp[i]。\n\n具体实现如下：\n\npython\ndef minimumTotal(triangle):\n n = len(triangle)\n dp = [0] * n\n dp[0] = triangle[0][0]\n for i in range(1, n):\n dp[i] = dp[i-1] + triangle[i][i]\n for j in range(i-1, 0, -1):\n dp[j] = min(dp[j], dp[j-1]) + triangle[i][j]\n dp[0] += triangle[i][0]\n return min(dp)\n\n\n这样，我们只使用了两个一维数组来存储中间结果，空间复杂度为O(n)，优化了原先O(n^2)的空间复杂度。