初始空集 dp[i]表示子问题A[..i)，则元素访问要用A[i-1]，i>=1，初始空集在dp[0]； dp[i]表示子问题A[i..]，则元素访问仍用A[i]，初始空集在超出结尾的dp[N]。

遍历顺序：某一维上看递推式的依赖项来自哪个方向。比如dp[i][j] = dp[i+1][j-1]，在i维上从右往左遍历、在j维上从左往右遍历。

  • 若某些维度提供了全部初始值，这些维度上的遍历顺序可任意。比如
    • student-attendance-record-ii提供了初始切面上a,l维的全部初始值，a,l维的遍历顺序可任意。
    • scramble-string提供n==1切面上i,j维的全部初始值，i,j维的遍历顺序可任意。
    • remove-boxes提供了i=j切面上k∈[0,i]范围的全部初始值，k维在[0,i]内的遍历顺序可任意。

维度省略：递推式在某一维上只依赖前一项，可以省掉这一维。比如dp[i][j] = dp[i-1][j]，在i维上只依赖dp[i-1][]，可以省掉i这维，i这维的遍历顺序保持不变。

  • 默认降维要使用临时变量ndp[]。这是为简化判断，等效于不降维。

    • ndp[]在循环内的初始化要符合递推式的初始化。
    • 三维降维，一定要用临时变量。这是为简化判断。

  • 二维降维若不用临时变量，剩余那维的遍历顺序都是从新状态到旧状态，可记作"旧逆新正"。

    1. 赋值右边有旧状态（如 dp[i+1][]或dp[i-1][]）。比如 dp[i][j] = dp[i+1][j-1]，省掉i这维，i保持从右往左遍历，j要从右往左遍历（"旧逆"）。
    依赖旧状态，降维后剩余那维的遍历顺序从新状态到旧状态。

列举所有情况：
* 若dp[i][j] = dp[i+1][j-1]，省掉i这维，i保持从右往左遍历。dp[j] = dp[j-1]，要让dp[j-1]是旧状态，j要从右往左遍历；
* 若dp[i][j] = dp[i+1][j+1]，省掉i这维，i保持从右往左遍历。dp[j] = dp[j+1]，要让dp[j+1]是旧状态，j要从左往右遍历；
* 若dp[i][j] = dp[i+1][j]，  省掉i这维，i保持从右往左遍历。dp[j] = dp[j]，  要让dp[j]是旧状态，  j可任意顺序遍历；
* 若dp[i][j] = dp[i-1][j-1]，省掉i这维，i保持从左往右遍历。dp[j] = dp[j-1]，要让dp[j-1]是旧状态，j要从右往左遍历；
* 若dp[i][j] = dp[i-1][j+1]，省掉i这维，i保持从左往右遍历。dp[j] = dp[j+1]，要让dp[j+1]是旧状态，j要从左往右遍历；
* 若dp[i][j] = dp[i-1][j]，  省掉i这维，i保持从左往右遍历。dp[j] = dp[j]，  要让dp[j]是旧状态，  j可任意顺序遍历。
    1. 赋值右边有新状态（如 dp[i][]）。比如完全背包问题dp[i][j] = max( dp[i-1][j], dp[i][j-c] + w )，省掉i这维，dp[j-c]要表示新状态dp[i][j-c]，j要从左往右遍历（"新正"）。
    2. 若赋值右边同时有新旧状态，而新旧状态对剩余那维要求的遍历顺序不同，只能用临时变量。

自顶向下带memo的递归写法，都可以改成自底向上的dp写法

  • 几个参数就是几维dp
  • 递归终止条件就是dp的初始赋值
  • 递归主体部分要放到循环中，几个参数就是几重循环
  • 递归调用子问题就是对其他dp值的使用