题意分析

  • 给你一个序列，我们需要选取其中几个数字拼接成一个固定的数字，问不同的拼接方案？

思路分析 DP

解法一

  • 首先，我们来分析一下，这个题目需要n种数字拼接成一个固定的数字x，假设我们当前已经知道了前i-1种数字的情况凭借成x的方案数，那么当我们枚举到第i种数字的时候，我们拼接的方案数就可以由前i-1种情况转移过来。具体的转移方程就是.初始条件为

  • 代码如下

    • 最外层每次次，第二层枚举次，里面枚举次，所以总的时间复杂度就是
    • 状态方程定义为，前种硬币组合成的种类数，所以空间复杂度为 
class Solution {
public:
    /**
     * 
     * @param n int整型 ：牛币值种类数
     * @param x int整型 ：牛妹拥有的钱数
     * @param a int整型vector<vector<>> ：第二个vector中的第一列表示币值，第二列表示牛牛拥有币值的个数
     * @return int整型
     */
    int dp[55][110];
    int solve(int n, int x, vector<vector<int> >& a) {
        // write code here
        // 枚举使用的硬币的种类数
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            // 枚举前i种硬构成面值j的种类数
            for(int j=0;j<=x;j++){
                // 枚举当前这种硬币使用的个数
                for(int k=0;k<=a[i-1][1]&&j-k*a[i-1][0]>=0;k++){
                    dp[i][j]+=dp[i-1][j-k*a[i-1][0]];
                }
            }
        }
        return dp[n][x];
    }
};

解法二

  • 我们使用滚动数组优化空间。我们观察上面的状态方程，我们发现，每种状态只能由上一个状态转移过来。所以其实我们状态方程的第一维可以定义为两个状态，但是在每次处理当前状态的时候我们需要将当前的状态先清0，防止之前的状态的影响。

  • 如下图

图片说明

  • 所以其实这个状态i-1之前的是什么状态我们根本不关心，故可以进行上述优化

  • 代码如下

    • 最外层每次次，第二层枚举次，里面枚举次，所以总的时间复杂度就是
    • 状态方程定义为，第种状态硬币组合成的种类数，所以空间复杂度为 
class Solution {
public:
    /**
     * 
     * @param n int整型 ：牛币值种类数
     * @param x int整型 ：牛妹拥有的钱数
     * @param a int整型vector<vector<>> ：第二个vector中的第一列表示币值，第二列表示牛牛拥有币值的个数
     * @return int整型
     */
    int dp[2][110];
    int solve(int n, int x, vector<vector<int> >& a) {
        // write code here
        // 枚举使用的硬币的种类数
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            // 枚举前i种硬构成面值j的种类数
            for(int j=0;j<=x;j++){
                dp[i&1][j]=0;
            }
            for(int j=0;j<=x;j++){
                // 枚举当前这种硬币使用的个数
                for(int k=0;k<=a[i-1][1]&&j-k*a[i-1][0]>=0;k++){
                    dp[i&1][j]+=dp[(i-1)&1][j-k*a[i-1][0]];
                }
            }
        }
        return dp[n&1][x];
    }
};

解法三

  • 我们继续进行优化，我们观察第二种写法，我们发现，我们枚举x的硬币数对应的种类的时候，都是由x之前的状态转移过来的，所以其实我们没有必要考虑第一维。直接让第二维由之前的状态转移过来就行了。所以状态方程就变为一维的了。

  • 代码如下

    • 最外层每次次，第二层枚举次，里面枚举次，所以总的时间复杂度就是
    • 状态方程定义为，硬币组合成的种类数，所以空间复杂度为 
class Solution {
public:
    /**
     * 
     * @param n int整型 ：牛币值种类数
     * @param x int整型 ：牛妹拥有的钱数
     * @param a int整型vector<vector<>> ：第二个vector中的第一列表示币值，第二列表示牛牛拥有币值的个数
     * @return int整型
     */
    int f[120];
    int solve(int n, int x, vector<vector<int> >& a) {
        // write code here
        memset(f,0,sizeof(f));
        f[0]=1;
        for(int i=0;i<n;i++){
           for(int j=x;j>0;j--){
               // 这里注意k不能从0开始了，不然会重复计算
               for(int k=1;k<=a[i][1]&&j>=k*a[i][0];k++){
                   f[j]+=f[j-k*a[i][0]];
               }
           }
        }

        return f[x];
    }
};