动态规划如果两个状态变量如何解决呢？

Question

看视频的时候想到了如果动态规划的时候，状态变量是两个的话，有点不知道怎么解决了。比如，一个状态变量的集合在A

中，一个状态变量的集合是B，从A中找出一个数，再对应的从B中找出一个数相乘，使得最后中乘机之和最大。A和B的集合中元素相等。

Answer 1

提问者 蓝胖子的编程梦 2017-12-19 21:32:35

或者说老师，我提的这个问题没有重叠子问题的现象，只有最优子结构，这算动态规划吗？有点像错位问题了(O_O)？

• liuyubobobo #1

  如果没有重叠子问题，可以使用动态规划的方式做，但这样做达不到动态规划本身的提速目的。最优子结构保证了动态规划求最优解的正确性；重叠子问题保证了高效性。正是因为有重叠子问题，使得重复状态不需要重复计算，才有动态规划这种方法的优势。
  
  至于有两个状态，是正常的。继续往下看，无论是背包问题还是LCS，都有两个状态。但是也拥有重叠子问题。