整数划分

题目描述

一个正整数n可以表示成若干个正整数之和，形如：$n=n1+n2+…+nk$， 其中 $n1≥n2≥…≥nk,k≥1$

我们将这样的一种表示称为正整数n的一种划分。 现在给定一个正整数n，请你求出n共有多少种不同的划分方法。

---

本题有多种解法:

总思路

参考完全背包问题的思路, 将题目转化为容量为 $n$ 的背包, 有价值和体积相同的的物品$1,2,3,...,n$ .这里要求的是恰好将背包装满. ( 之前的背包问题是不用装满的, 只要价值最大即可)

解法一

$dp[\ \ i\ \ ][\ \ j\ \ ]$ (朴素算法入手)记录的是由 $1\sim i$ 恰好得到 $j$ 的方案数.

状态计算： $dp[i][j]=dp[i-1][j]+dp[i-1][j-i]+dp[i-1][j-2*i]+...+dp[i-1][j-s*i]$

$$dp[i][j-i]=dp[i-1][j-i]+dp[i-1][j-2*i]+...+dp[i-1][j-s*i]$$

因此

$$dp[i][j]=dp[i-1][j]+dp[i][j-i]$$

$\textcolor{cyan}{其中,s为j能容纳的最大i的个数}$

通过滚动数组优化, 得到:

$$dp[j]=dp[j]+dp[j-i]$$

简单分析一下:

• 采用顺序遍历, 因此在用到 $dp[j-i]$ 时, 已经被更新为 $dp[i][j-i]$ 了, 而右式中的 $dp[j]$ 是左值自增前的自己. 所以你甚至可以写成:

$$dp[j]+=dp[j-i]$$

• 但是由于有时数据值过大需要取模, 此时不能用+=.

• 因此我们可以理解为: $1\sim i$ 得到 $j$ 的方案数等于由 ${1\sim (i-1)}$ 得到 $j$ 的方案数加上一定用上 $i$ 的方案数$\textbf{\textcolor{gold}{(即从一定含有i的方案中取走一个i)}}$

这时候我们可以发现, DP中的状态表示的是一种相当抽象的形式, 甚至在这里的 $dp[j-i]$ 的状态含义是相对于 $dp[j]$ 而言的.

核心代码如下:

for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            f[j]=(f[j]+f[j-i])%mod;
    //f[n]%=mod;
    cout<<f[n];

解法二

$dp[\ \ i\ \ ][\ \ j\ \ ]$ 记录的是由 $i$ 个数构成的, 值恰好是 $j$ 的方案数.

状态计算:

$$dp[i][j]=dp[i-1][j-1]+dp[i][j-i]$$

$\textbf{\textcolor{gold}{计算依据是最小值值是否是1}}$
这里我们可以进一步发现, dp的状态计算只要满足不重不漏的原则, 就可以进行抽象的划分

利用滚动数组进行优化:

• $\textcolor{gold}{会发现没法优化}$hh, 因为右式调用了本层和上一层的, 在 $j$ 同侧(都小于 $j$ )的 $dp$ 值. 这是顺序和逆序遍历都无法解决的问题.