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

来源：9-4 状态的定义和状态转移 House Robber

蓝胖子的编程梦

2017-12-19

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

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

写回答

1回答

蓝胖子的编程梦

提问者

2017-12-19

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

liuyubobobo

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

2017-12-20

共1条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7410 学习 · 1150 问题

查看课程

相似问题

针对279题使用动态规划求解

回答 1

kmp算法是否属于动态规划？

回答 1

动态规划的状态定义

回答 1

动态规划

回答 1

请问如何将记忆化搜索解法转成动态规划写法

回答 2

打开慕课网App查看更多内容