动态规划-322零钱兑换

  翻了半天没找到c++的记忆化搜索，我在纠结记忆数据的数组是作为共享变量，还是作为参数一直在函数中传递。

  首先我想在函数外定义个vector，然后在函数内resize大小并赋值，可以免除help在递归函数中传递，但是失败了。后来我尝试了int *help；在函数内new空间，但是也失败了。怎么办呢？没有完成我想的那样，但是下面的也可以通过题解。，，，，直接递归超时了。

    int coinChange(vector& coins, int amount) {
        if(amount==0) return 0;
        if(amount<0)  return -1;
        int res=amount+1;
        for(int coin:coins){
            int subproblem= coinChange(coins,amount-coin);
            if(subproblem==-1){
                continue;;
            }
            res=min(res,subproblem+1);
        }
        return res==amount+1?-1:res;//避免res并没有赋值，还传回去amount+1

    }

class Solution {
public:
    int coinChange(vector& coins, int amount) {
        int *help=new int[amount+1]; //记忆数组
        fill (help,help+amount+1,-2);//赋值-2，代表该amount的结点还没有获得
        sort(coins.begin(), coins.end());//将coins排序，后续可以加一下优化
        return dp(coins,amount,help);
    }

    int dp(vector& coins, int amount,int help[]) {

        if(amount==0) return 0;  //凑成0需要0个。。。
        if(amount<0) return -1;  //凑成负的不可能的，给个-1
        if(help[amount]!=-2) return help[amount];  //记忆数组里已经有了，直接用
        int res=amount+1; //amount+1是不可能超过的个数

        for (int c:coins){
            int subproblem= dp(coins,amount-c,help); //树形往下走
            if(subproblem==-1){  //负的不可能的，不进行计数
                continue;
            }

            res= min(res,subproblem+1); //通过coins.size次比较，获取兄弟几个最少用的个数
                                        //+1是因为从兄弟到他们的父节点还要加1，即amount-c的那一步
        }

        return  help[amount] = (res == amount+1) ? -1 : res; //res == amount+1避免已经到最下结点

    }
};

    int coinChange(vector& coins, int amount) {
        vector help(amount+1,amount+1); //有个base0，所以amount+1，仍然赋值不可能的数
        help[0]=0;
        for(int i=0;i<=amount;i++){ //状态：从0开始一个一个自底向上开始获取
            for(int coin:coins){ //选择：硬币金额
                if((i-coin)<0) continue;//小于0，不可能凑出
                help[i]=min(help[i],help[i-coin]+1);  
                **//其实，help[i]=min((coins,i-coin1),(coins,i-coin2),(coins,i-coin5))+1**
            }
        }
        if (help[amount] == amount + 1)
            return -1;
        //如果可以凑出，就直接返回最终值即可
        return help[amount];

    }