[数据结构与算法]动态规划——题目：整数拆分

题目链接

自己的思考过程

这道题我没有做出来，在讲正确解法之前，这里记录一下我的思路偏差。

1. 我是先按着题目的拆分思路，把N拆分为多个1、多个1和2、多个1和2和4........
2. 然后发现N若为奇数，则f(N) = f(N-1)，因为奇数不管怎么样都会有个1多余出来。
3. 对于N为偶数的情况，我就一直在思考怎么样让f(N) = F(f(N-2))，很明显，这个关系F我没有找出来。因为N-(N-2) = 2，所以我分了两个可能，一个是(N-2)+2，另一个是(N-2)+1+1。若先取(N-2)+2的情况，则(N-2)+1+1需要寻找(N-2)所有方法中不包含2的那些方法，这样才不会与(N-2)+2的情况重复。然后自己就一直陷在这个死胡同里

较好解法一

1. 对于一个数字 n，如果 n 是奇数，那么 n 的所有组合方式中一定包含一个 1，那么它和 n-1 的组合方式种数相同，dp[n] = dp[n-1]；
2. 如果 n 是偶数，那么它的组合方式中可能有 1，也可能没有 1，有 1 的组合方式有 dp[n - 1] 种，没有 1 的组合方式有 dp[n/2] 种，因为偶数组合方式除以 2 后的组合方式其实是一样的，dp[n] = dp[n-1] + dp[n/2]

我前面的思路与这个解法很接近，与该解法的主要差异在于：

• 我一直关注于N+2跟N相比，要么"+2"、要么"+1+1"，就想分别找出"+2"对应多少种方法、"+1+1"对应多少种方法，然后就把问题复杂化
• 而这个解法的关注点在于，组合方式中是否包含1，从而简化了问题

这让我不禁回忆起做 放苹果?这个题时，我当时的关注点放在了拆分的动态过程，而没有想到去关注 是否有空盘子?。

做了这两题，我被动态规划思维的抽象与简洁性所惊叹，也隐约觉得，以后遇到DP问题时，对状态转移的过程，尽量向“?某集合是否包含某特殊值?”这个方向上靠。

代码

#include <iostream>
using namespace std;
const int MAXN=1000000+1;
const int MOD=1000000000;
int main(){
    int N,dp[MAXN];
    dp[1]=1;
    for(int i=2;i<MAXN;i++){
        if(i%2==1) dp[i] = dp[i-1];
        else dp[i] = (dp[i-1]+dp[i/2])%MOD;
    }
    while(cin>>N){
        cout<<dp[N]<<endl;
    }
    return 0;
}

较好解法二

可以看做一个完全背包——求恰装满背包时的方案总数问题

1. 每一个拆分必须是1,2,4,2^3,...2^19(考虑n最大为10^6)
2. 相当于现在有20种物品,第i种物品的花费是2^(i-1),每一种可以重复取, dp[i][j]表示前i种物品恰装满容量为j的物品时的方案总数, 从而dp[i][j] = dp[i-1][j] + dp[i][j-a[i]]

代码

#include <iostream>
using namespace std;
const int MAXI=20+1;
const int MAXN=1000000+1;
const int MOD=1000000000;
int arr[MAXI],dp[MAXN];
void Initial(){
    arr[1] = 1;
    for(int i=2;i<MAXI;i++){
        arr[i] = ((arr[i-1]*2)%MOD);
    }
}
int main(){
    int N;
    Initial();
    while(cin>>N){
        for(int j=0;j<=N;j++){
            dp[j]=0;
        }
        for(int i=1;i<MAXI;i++){
            for(int j=arr[i];j<=N;j++){
                if(j==arr[i]) dp[j] = (dp[j]+1)%MOD;   // 这一步的判断很重要
                else dp[j] = (dp[j]+dp[j-arr[i]])%MOD;
            }
        }
        cout<<dp[N]<<endl;
    }
    return 0;
}