动态规划的设计思想 动态规划(DP)[1]通过分解成子问题解决了给定复杂的问题,并存储子问题的结果,以避免再次计算相同的结果。我们通过下面这个问题来说明这两个重要属性:重叠子问题和最优子结构。 重叠子问题 像分而治之,动态规划也把问题分解为子问题。动态规划主要用于:当相同的子问题的解决方案被重复利用。在动态规划中,子问题解决方案被存储在一个表中,以便这些不必重新计算。因此,如果这个问题是没有共同的(重叠)子问题, 动态规划是没有用的。例如,二分查找不具有共同的子问题。下面是一个斐波那契函数的递归函数,有些子问题被调…

2016年10月28日 0条评论 6点热度 阅读全文

众所周知,递归的实现是通过调用函数本身,函数调用的时候,每次调用时要做地址保存,参数传递等,这是通过一个递归工作栈实现的,同时影响效率的。递归是利用系统的堆栈保存函数当中的局部变量来解决问题的,而递归就是在栈处理栈上一堆的指针指向内存中的对象,这些对象一直不被释放,直到递归执行到最后一次后,才释放空间. 循环效率与递归效率 递归与循环是两种不同的解决问题的典型思路。当然也并不是说循环效率就一定比递归高,递归和循环是两码事,递归带有栈操作,循环则不一定,两个概念不是一个层次,不同场景做不同的尝试。 递归通常很直白地描…

2015年9月24日 0条评论 4点热度 阅读全文

众所周知,递归的实现是通过调用函数本身,函数调用的时候,每次调用时要做地址保存,参数传递等,这是通过一个递归工作栈实现的,同时影响效率的。递归是利用系统的堆栈保存函数当中的局部变量来解决问题的,而递归就是在栈处理栈上一堆的指针指向内存中的对象,这些对象一直不被释放,直到递归执行到最后一次后,才释放空间. 循环效率与递归效率 递归与循环是两种不同的解决问题的典型思路。当然也并不是说循环效率就一定比递归高,递归和循环是两码事,递归带有栈操作,循环则不一定,两个概念不是一个层次,不同场景做不同的尝试。 递归通常很直白地描…

2015年9月24日 0条评论 1点热度 阅读全文