首页 > 代码库 > 动态规划学习笔记(不定期更新)

动态规划学习笔记(不定期更新)

最近刚开始接触动态规划(Dynamic Programming)算法,之前略有耳闻,一直觉得DP非常之高大上,看了某些题的DP解法也是云里雾里,哇擦?!这么几行代码就解决了?怎么全是数组操作?时间复杂度也很低的样子。其实不然,当我真正开始学习动态规划的时候才发现这货没那么玄乎。

把我对DP浅显的理解总结为以下几点:

1.空间换时间。

2.找到状态。

3.找到状态转移方程。

动态规划是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。为了能够快速的不重复的计算出最终解,所以需要保存每次状态的值,空间换时间就是这么个意思。

我举个最简单的例子,也是我看到动态规划后自己想到的,这个问题我们每个人学编程肯定都碰到过,斐波那契数列问题。好,我就按照我之前讲的理解来分析这题,先找到问题的状态,很明显不就是每次计算出来的这个值么。然后是状态转移方程,这更明显了,不就是斐波那契数列的定义么:f(n)=f(n-1)+f(n-2)。所以我觉得拿这题来入门动态规划再好不过了。之前的解法是递归,递归虽然简单易理解但是有大量的重复计算,效率极低,并且有函数栈溢出的危险,现在我们定义了状态和状态转移方程,代码就很好写了,保存每次的计算结果,最后一个结果就是整个问题的解。然后这个解法可以优化的,我们发现其实不用每次都保存中间结果,因为我们计算下一个状态时只需要上两次的结果,所以每次只要保存上两次的结果就可以了,这样空间复杂度也降到了常数级别,时间效率也大大增加。

代码如下:

int fib(int n){	if(n==0||n==1) return n;	int fia=0;	int fib=1;	int result=0;        	for(int i=2;i<=n;i++)	{ 		result=fia+fib;  //关键!状态转移方程!		fia=fib;		fib=result;	}	return result;}

  

 

这个代码非常简单,谁都会写,我在学习动态规划之前就已经熟练可以写出上面的代码了,但是最最重要的是之前用动态规划思想分析的过程!动态规划是个庞大的话题,入门容易(我还没入门),想要真正理解DP的意义我还有很长的路要走,欢迎各位大神指点迷津。

本博客中LeetCode相关题目(陆续更新):

Unique Binary Search Trees
本博客内容与代码均为作者Jarvis原创,如若转载请注明。

动态规划学习笔记(不定期更新)