n种币值x1，x2，··，xn,和总钱数M都是正整数，如果每种币值的钱币至多使用1次,问:对于 M 是否可以有一种找零钱的方法?设计一个算法求解上述问题。说明算法的设计思想,分析算法最坏情况下的时间复杂度

这是一个典型的0/1背包问题，可以使用动态规划算法求解。

具体思路如下：

1. 定义一个二维数组dp，其中dp[i][j]表示使用前i种币值，能否凑出总钱数为j的零钱。

2. 初始化dp数组，当总钱数为0时，任何币值都可以不选，所以dp[i][0] = true；当没有任何一种币值可选时，无法凑出任何总钱数，所以dp[0][j] = false。

3. 对于每一个币值x[i]，遍历总钱数j，如果j >= x[i]，则可以选择使用或者不使用这个币值，因此有两种情况：

- 不使用x[i]，此时凑出总钱数j的情况与使用前i-1种币值凑出总钱数j的情况相同，即dp[i][j] = dp[i-1][j]。

- 使用x[i]，此时需要凑出总钱数j-x[i]，而且不能再使用x[i]了，即需要使用前i-1种币值凑出总钱数j-x[i]，即dp[i-1][j-x[i]]。因此有dp[i][j] = dp[i-1][j-x[i]]。

4. 最终的解为dp[n][M]，即使用前n种币值，能否凑出总钱数为M的零钱。

算法的时间复杂度为O(nM)，空间复杂度为O(nM)。

以下是C++代码实现：

bool canFindChange(int M, vector<int>& coins) {
    int n = coins.size();
    vector<vector<bool>> dp(n+1, vector<bool>(M+1, false));
    // 初始化
    for (int i = 0; i <= n; i++) dp[i][0] = true;
    for (int j = 1; j <= M; j++) dp[0][j] = false;
    // DP
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= M; j++) {
            if (j >= coins[i-1]) {
                dp[i][j] = dp[i-1][j] || dp[i-1][j-coins[i-1]];
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[n][M];
}