标签归档:编程

动态规划小结

一个入门级见解和总结

动态规划实际上意思就是计算的时候需要根据之前的结果来继续计算, 英文dynamic programming,动态编程的意思,在编程的时候本质上是枚举大量场景下的最优解,例如计算dp[a][b],的所有值,然后二维表,其中每个dp都是特定场景的最优解,但是我们可能最后只采用其中一个场景,计算其他场景的最优解是为了算出目标场景的最优解

解决动态规划问题可以分为四步

第一步 确定定义和状态

确定状态(描述一个场景要几维),然后转化为子问题(n推到n+1或者n-1)

什么是状态:所有会影响所定义的值(dp)计算的因素都是状态,但我们需要只选择最少且独立和必要的,如果两个状态可以互相推导,那么只选其中之一 查看更多