动态规划算法的优缺点(动态规划算法)
精选百科
2024-06-29 17:10:31
导读 大家好,小问来为大家解答以上问题。动态规划算法的优缺点,动态规划算法这个很多人还不知道,现在让我们一起来看看吧!1、其实你可以这么去...
大家好,小问来为大家解答以上问题。动态规划算法的优缺点,动态规划算法这个很多人还不知道,现在让我们一起来看看吧!
1、其实你可以这么去想。
2、 能用动态规划解决的问题,肯定能用搜索解决。
3、 但是搜素时间复杂度太高了,怎么优化呢? 你想到了记忆化搜索,就是搜完某个解之后把它保存起来,下一次搜到这个地方的时候,调用上一次的搜索出来的结果。
4、这样就解决了处理重复状态的问题。
5、 动态规划之所以速度快是因为解决了重复处理某个状态的问题。
6、 记忆化搜索是动态规划的一种实现方法。
7、 搜索到i状态,首先确定要解决i首先要解决什么状态。
8、 那么那些状态必然可以转移给i状态。
9、 于是你就确定了状态转移方程。
10、 然后你需要确定边界条件。
11、 将边界条件赋予初值。
12、 此时就可以从前往后枚举状态进行状态转移拉。
以上就是【动态规划算法的优缺点,动态规划算法】相关内容。
猜你喜欢