动态规划问题

动态规划问题是一种分而治之的策略,需要确定动态规划的三个要素:

    (1)问题的各个阶段 

    (2)每个阶段的状态(用什么信息做状态?)

    (3)从前一个阶段转化到后一个阶段之间的递推关系。

递推关系可能写出来,比如数学计算大小等优化问题,也可能写不出来,例如字符处理优化问题就只能通过叙述来完成。


动态规划思想有递推的思想,但是优点就是避免了计算重复的数据,减少了时间复杂度,代价就是增加了空间复杂度。

动态规划问题由思考到编程实现:

    (1)从大到小分析,从外到内分析,也即得出 F(i,j) = Max{F(i-1,j), F(i,j-1)} + A(i,j),再分析细节;

    (2)从小到大求解,从内到外求解,也即先得出F(0,0), F(0,1), F(1,0) ..... 再求后面的 F(i-1,j), F(i,j-1), F(i,j);

动态规划有类似累积的性质,例如“累加”、“累乘”等等;


[1] java 动态规划策略原理及例题.http://blog.csdn.net/QuinnNorris/article/details/77484573(此文章包含动态规划问题的编程实现,可以理解编程实现的细节对比)

[2] java算法之动态规划基本思想以及具体案例.http://blog.csdn.net/likailonghaha/article/details/53561646(此文章可以作为上面的补充,从其他角度理解动态规划的特点)

[3] 动态规划.http://www.cppblog.com/menjitianya/archive/2015/10/23/212084.html.(此文章总结的比较好,可以重点参考)

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

友情链接更多精彩内容