1

I am reading up dynamic programming chapter of Introduction to Algorithms by Cormen et al. I am trying to understand how to characterize the space of subproblems . They gave two examples of dynamic programming . Both these two problems have an input of size n

  1. Rod cutting problem (Cut the rod of size n optimally)
  2. Matrix parenthesization problem .(Parenthesize the matrix product A1 . A2 .A3 ...An optimally to get the least number of scalar multiplications)

For the first problem , they choose a subproblem of the form where they make a cut of length k , assuming that the left subproblem resulting from the cut can not be cut any further and the right subproblem can be cut further thereby giving us a single subproblem of size (n-k) .

But for the second problem that choose subproblems of the type Ai...Aj where 1<=i<=j<=n . Why did they choose to keep both ends open for this problem ? Why not close one end and just consider on subproblems of size (n-k)? Why need both i and j here instead of a single k split?

4

2 回答 2

3

这是一门艺术。动态规划问题的类型很多，要定义一种方法来计算出我们想要解决子问题的空间维度并不容易。

这取决于子问题如何相互作用，并且很大程度上取决于空间的每个维度的大小。

动态编程是描述子问题的缓存或记忆以更有效地解决更大问题的通用术语。但是有很多不同的问题可以通过动态规划以多种不同的方式解决，我无法解释全部，除非你有一个特定的动态规划问题需要解决。

我所能建议的就是在解决问题时尝试：

  • 如果你知道如何解决一个问题，你可以使用类似的技术来解决类似的问题。
  • 尝试不同的方法，并根据每个维度的输入大小估计复杂性的顺序（时间和内存），然后给定每个维度的大小，看看它是否执行得足够快，并且在内存限制内。

一些可以被描述为动态规划的算法包括：

于 2012-09-05T10:01:18.797 回答
2

Vazirani 关于动态编程的技术说明 http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf 有一些有用的方法可以在给定输入的情况下创建子问题。我在下面的列表中添加了一些其他方法：

  1. 输入 x_1、x_2、..x_n。子问题是 x_1...x_i。

  2. 输入 x_1, x_2....x_n。子问题是 x_i, ...x_j。

  3. 输入 x_1, x_2...x_n 和 y_1, y_2..y_m。子问题是 x_1, x_2, ..x_i 和 y_1, y_2, ..y_j。

  4. 输入是有根树。子问题是有根子树。

  5. 输入是一个矩阵。子问题是与原始矩阵共享一个角的不同长度的子矩阵。

  6. 输入是一个矩阵。子问题是所有可能的子矩阵。

通常使用哪些子问题取决于问题。尝试这些已知的变化，看看哪一个最适合您的需求。

于 2013-04-24T07:45:03.243 回答