1. 首页
  2. web前端

动态编程(Dynamic Programming)

本文素材来自视频,请自备梯子观看:What Is Dynamic Programming and How To Use It

Dynamic Programming:动态编程分为如下几步:

  1. 将复杂问题拆分成多个较简单的子问题
  2. 对每个子问题只计算一次,然后使用数据结构(数组,字典等)在内存中存储计算结果
  3. 子问题的计算结果按照一定规则进行排序(如,基于输入参数)
  4. 当需要再次运算子问题时直接使用已存储的计算结果而非再次运算以提升求解性能

这种存储计算结果以备再次使用称之为:Memoization(这个词,不知道怎么翻译好)

以斐波那契数列为例来说明:

1、使用递归实现:

def fib(n):     if n < 1:         raise ValueError('参数n必须为大于0的整数')     if n == 1 or n == 2:         return 1     return fib(n-2)+fib(n-1) 

这种方法是经典的递归运算。以fib(5)为例,整个求解过程可以拆分为:

动态编程(Dynamic Programming)

图片来自Youtube

我们可以看出,fib(2)被计算三次,fib(3)与fib(1)各被计算2次,时间复杂度为O(2^n)。

2、对递归进行改进

def fib_memory(n):     d = dict()     _fib_memory(n, d)   def _fib_memory(n, temp_dict):     if n < 1:         raise ValueError('参数n必须为大于0的整数')     if type(temp_dict) is not dict         raise TypeError('参数temp_dict必须为dict类型')     if n in temp_dict:         return temp_dict[n]     if n == 1 or n == 2:         result = 1     else:         result = fib_memory(n-1, temp_dict)+fib_memory(n-2, temp_dict)     temp_dict[n] = result     return result 

动态编程(Dynamic Programming)

图片来自Youtube

优化后,时间复杂度降为O(n)。优化后的算法依然使用了递归,当参数较大时(如,1000)会导致栈溢出:
RecursionError: maximum recursion depth exceeded in comparison

3、脱离递归:

def fib_bottom_up(n):     l = [None]*(n+1)     return _fib_bottom_up(n, l)  def _fib_bottom_up(n, temp_list):     if n < 1:         raise ValueError('参数n必须为大于0的整数')     if type(temp_list) is not list:         raise TypeError('参数temp_list必须为list类型')     if temp_list[n] is not None:         return temp_list[n]     if n == 1 or n == 2:         return 1     temp_list[1] = 1     temp_list[2] = 1     for i in range(3, n+1):         temp_list[i] = temp_list[i-1]+temp_list[i-2]     return temp_list[n] 
动态编程(Dynamic Programming)

图片来自Youtube

改进之后的算法不再使用递归,时间复杂度依然是O(n)。


对以上三种实现编写测试用例:

# coding=utf-8  import temp import unittest   class TestDif(unittest.TestCase):     def test_fib_0_throw_value_error(self):         with self.assertRaises(ValueError):             temp.fib(0)      def test_fib_1_return_1(self):         result = temp.fib(1)         self.assertEqual(1, result)      def test_fib_10_return_false(self):         result = temp.fib(10)         self.assertFalse(result == 10)      def test_fib_memory_10_return_false(self):         result = temp.fib_memory(10)         self.assertNotEqual(result, 10)      def test_fib_bottom_up_1000_return_true(self):         result = temp.fib_bottom_up(1000)         print(result)         self.assertTrue(result > 100000)   if __name__ == "__main__":     unittest.main() 

小结

无意中在Youtube上看到这段视频,就翻译整理下来与大家共享。

原文始发于:动态编程(Dynamic Programming)

主题测试文章,只做测试使用。发布者:开发工程师,转转请注明出处:http://www.cxybcw.com/3849.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code