计数类动态规划

例题：整数划分

基本思路 (完全背包)

可以把整数 \(n\) 看作容量为 \(n\) 的背包，物品的体积为 \(1\) 到 \(n\)，则可将本题转化为一个 完全背包问题，要求恰好装满背包。

• 状态表示： \(f(i,j)\)：
  • 集合：所有从 \(1\sim i\) 中选择，总体积恰好为 \(j\) 的选法；
  • 属性：选法的数量。
• 状态计算：按最后一个物品(第 \(i\) 个物品)选择了多少个来划分。
  • \(f(i-1,j)\)
  • \(f(i-1,j-i)\)
  • \(f(i-1,j-2i)\)
  • \(\cdots\)
  • \(f(i-1,j-si)\)

时间复杂度 \(O(n^2\log n)\)。

优化解法：

\[ f\left( i,j \right) =f\left( i-1,j \right) +f\left( i-1,j-i \right) +f\left( i-1,j-2\cdot i \right) +\cdots +f\left( i-1,j-s\cdot i \right) , \]

\[ f\left( i,j-1 \right) =f\left( i-1,j-1 \right) +f\left( i-1,j-2\cdot i \right) +\cdots +f\left( i-1,j-s\cdot i \right) ; \]

可得如下递推公式：

\[ \Longrightarrow f\left( i,j \right) =f\left( i-1,j \right) +f\left( i,j-i \right) \]

答案为 \(f(n,n)\)。

另一种思路

• 状态表示： \(f(i,j)\)：
  • 集合：所有总和为 \(i\)，并且恰好能表示成 \(j\) 个数的和的方案；
  • 属性：选法的数量。
• 状态计算：
• 所有表示的方案中 \(j\) 个数的的最小值为 \(1\)： \(f(i-1,j-1)\)；
• 所有表示的方案中 \(j\) 个数的的最小值大于 \(1\)： \(f(i-j,j)\)。

状态转移方程：

\[ f\left( i,j \right) =f\left( i-1,j-1 \right) +f\left( i-j,j \right) \]

答案为：

\[ \mathrm{answer}=f\left( n,1 \right) +f\left( n,2 \right) +\cdots +f\left( n,n \right) \]