dp
- DP如果只有一个起点,那除起点外都要初始化,如果任意状态都可以作为起点,则无需初始化。
- 一切问题从集合的表示出发
- 有部分题目是要初始化的,因为不是所有状态初始化都为0的。比如数字组合
- 最大、恰好、至少问题
- 重新理解:
- 所有只从前i个物品中选,且总体积
至多
是j
的情况 - 一个都不选,最大价值就是0
f(0, j)
都初始化是0,因为最大价值是0,所以f(0, j)=0
- 初始化方式:
f(0, j) = 0
恰好
- 只有f(0,0)是合法的,其余的f(0,j)都是不合法的, 因为一个都不选,
f[i][j]
的j不能为除0以外的任何数,就不符合集合的表示,所以要变成其他取不到的值(无穷); - 初始化方式:
f(0, 0) = 0, f(0, j) = INF/INF(取决于求最大值还是最小值)
- 只有f(0,0)是合法的,其余的f(0,j)都是不合法的, 因为一个都不选,
至少
- f(0, j),j是负数也是合法的。eg:j = -2,体积不管是5还是10还是什么大于-2的数,都是至少为-2的数,所以都是合法的
- 因为一个都不选,
f[i][j]
的j不能为除0以外的任何数,就不符合集合的表示,所以要变成其他取不到的值(无穷); - 初始化方式:
f(0, 0) = 0, f(0, j) = INF/INF(取决于求最大值还是最小值)
- 同时循环条件要更改
- 关于
正逆序
输出方案问题- 要求字典序最小输出,那么用
逆序
求状态,再用正序
求方案
- 要求字典序最小输出,那么用
注意
:某些题n和m不是按顺序的,输入时要注意