算法（三十一）

1、给一个函数，返回 0 和 1，概率为 p 和 1-p，请你实现一个函数，使得返回 0 1 概率一样

public int random(){
    int i = RANDOM();  
    int j = RANDOM();  
    int result;  

    while (true)  
    {  
        if (i == 0 && j == 1)  
        {  
            result = 0;  
            break;  
        }  
        else if (i == 1 && j == 0)  
        {  
            result = 1;  
            break;  
        }  
        else  
            continue;  
    }  

    return result;  
}

2、硬币1元，3元，5元，给定金额target，输出最少需要多少枚硬币

• 动态规划

public static int coinNum(int target) {
        int[] coin = {1,3,5};
        int[] dp = new int[target+1];
        for(int i=0;i<target+1;i++)
            dp[i] = i;
        for(int i=1;i<target+1;i++) 
            for(int j=0;j<coin.length;j++) 
                if(coin[j] <= i && dp[i-coin[j]]+1 < dp[i])
                    dp[i] = dp[i-coin[j]]+1;
        
        return dp[target];
    }

3、硬币1元，3元，5元，给定金额target，输出总过有多少种可能的组合方式？

public static int countWays(int target) {    

          int[] coin = {1,3,5};  

          int[] dp = new int[target+1];         

         dp[0] = 1;  

         for(int i = 0;i < coin.length;++i){  

                for(int j = coin[i];j <= target;++j){ 

                       dp[j] += dp[j-coin[i]];   

                }  

        }        

        return dp[target];    

}