二维dp空间压缩问题

hailuns · 6 January 2019 05:36

leetcode 322为例子
经过推到的二维表达式是
（前i种硬币凑到j的最小数量）
dp[i][j] = min {dp[i-1][j], dp[i][j-coins[i]]+1}

如何转成

dp[i] = min {dp[i], dp[i-coins[j]]+1}

网上就直接说了句因为dp[i]只和dp[i-1]有关
不是很明白

Xavier · 6 January 2019 05:44

这种都是需要先写出二维代码再改，不是表达式

直接通过表达式改跨度比较大

你可以先贴下二维的代码

Xavier · 6 January 2019 05:58

概念上分析一下空间如何压缩

如图，dp[i][j] 其实只需要通过第i行和第i-1行就可以计算出，i-2行及前面都不需要。
也就是我们只需要一个一维数组来保存前一行的数据即可。

Xavier · 6 January 2019 06:09