Method Of Four Russians

Published: by Creative Commons Licence

  • Tags:

对于二维动态规划,此时动态规划对应的dp数组为一个n*n矩阵。如果动态规划的每一项仅依赖于其左边和其上边的一个项(即dp[i][j]可以通过dp[i-1][j]与dp[i][j-1]计算得到),那么我们可以对其应用一个查表优化。

假设dp每一项的取值范围为1到c,共c个值。我们按下面步骤优化二维DP数组的计算:

  1. 我们将dp矩阵划分为t*t的小矩阵。
  2. 每个小矩阵均由有其左边界和上边界共同决定,因此小矩阵总共可能有c^(2t-1)种,这里按c^(2t)简化计算。我们将所有可能的矩阵打表记录其值。换言之维护一个表,输入为左上边界,输出为右下边界。每个矩阵需要的计算量为O(t^2),故总计算量为O(t^2*c^(2t))。
  3. 我们通过表分别计算每一个大矩阵中划分得到的小矩阵。共(n/t)^2个小矩阵,每次利用之前的表进行查询,每个小矩阵费时O(2t),故总的时间费用为O(n^2/t)。

综合以上,我们总共需要时间复杂度O(t^2*c^(2t)+n^2/t),空间复杂度为O(t*c^(2t)+n)

选择t为logc(n)/2,代入结果为时间复杂度O(n(logc(n)^2)+n^2/logc(n))=O(n^2/logc(n)),空间复杂度为O(nlogc(n))