扣一张链接里的图
https://www.sohu.com/a/153858619_466939
不管怎样,先看最终状态,看它由谁派生过来。 在动态规划里,所有的点都要算一遍,但只保留到该点的最优状态。每点的最优状态等于上一步骤的两个状态的最优中再取最优
一维
找要解决的最大对象(楼梯),要解决的问题属性步数。只有一个限定条件怎么走,一维dp。可以选的是走一步还是走两步,可选的情况每一步都有具体值,不是是否问题,找方程 。
看最终状态是由哪几种情况一步得到,那么最终状态就等于这几种情况的和,求出一种表达式来,推广到由下到上的过程,就能写出迭代形式
二维
这里最大的对象是矿,人数和金钱都是矿的附属品,这里要考虑的收益的依附对象是矿所以一重循环是矿。可以选的是挖还是不挖。有两个限定条件,矿的选择,人数(二维)。是否问题用min,max。
考虑要解决对象(矿)的问题(价钱(价钱也是对象一种属性)最高等),根据对象另一个属性(人数),在限定多少人的条件下计算挖到某座矿的时候的能得到的最大收益,即是不挖这座矿(子矿人数不会减少,直接找子矿在这个限定人数下的最优解)还是挖这座矿(选择挖的时候子矿的人数会减少,所以要找子矿减掉一定人数时候的最优解)。
这里面一重循环是矿的个数(最大的对象),二重循环就是限定的人的个数(最大对象的一个属性,而且是除去问题中的属性的那个属性)