1-找零钱问题

  public int countWays(int[] penny, int n, int aim) {
//        return violence(penny, 0, aim);
            int[][]map=new int[n+1][aim+1];
            return violence(penny, 0, aim, map);
    }
    //暴力求解法
    public int violence(int[] penny, int start, int aim){
            int res=0;
            if(start==penny.length){
                        res=aim==0?1:0;
            }else{
            for(int i=0;i*penny[start]<=aim;i++){
                        res+=violence(penny, start+1, aim-i*penny[start]);
            }
            }
            return res;
    }

    //记忆搜索法
    public int violence(int[] penny, int start, int aim,int[][] map){
            int res=0;
            if(start==penny.length){
                        res=aim==0?1:0;
            }else{
            for(int i=0;i*penny[start]<=aim;i++){
                        int value=map[start+1][aim-i*penny[start]];
                        if(value==0){
                                    res+=violence(penny, start+1, aim-i*penny[start],map);
                        }else{
                                    res+=value;
                        }
            }
            }
            map[start][aim]=res;
            return res;
    }
    //动态规划法
    public int dynamic(int[] penny, int n, int aim){
        int[] dp = new int[aim+1];
        for(int i = 0;i <= aim;i++)
            if(i % penny[0] == 0)
                dp[i] = 1;

        for(int i = 1;i<n; i++)
            for(int j = 1;j<=aim;j++)
                if(j>=penny[i])
                    dp[j] += dp[j-penny[i]];
        //相当于dp[i][j]=dp[i-1][j]+dp[i][j-penny[i]]

        return dp[aim];
    }