首页 > 试题广场 >

拼凑硬币

[编程题]拼凑硬币

热度指数：6718 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

小Q十分富有，拥有非常多的硬币，小Q拥有的硬币是有规律的，对于所有的非负整数K，小Q恰好各有两个面值为2^K的硬币，所以小Q拥有的硬币就是1,1,2,2,4,4,8,8,…。小Q有一天去商店购买东西需要支付n元钱，小Q想知道有多少种方案从他拥有的硬币中选取一些拼凑起来恰好是n元（如果两种方案某个面值的硬币选取的个数不一样就考虑为不一样的方案）。

输入描述:

输入包括一个整数n(1≤n≤10^18)，表示小Q需要支付多少钱。注意n的范围。

输出描述:

输出一个整数，表示小Q可以拼凑出n元钱放的方案数。

示例1

输入

输出

算法知识视频讲解

Java

牛客665590250号

动态规划
import java.util.*;

public class Main{
    public static void  main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            long n = sc.nextLong();
            System.out.println(helper(n));
        }
    }
    static long helper(long n){
        List<Integer> list = new ArrayList<>();
        while(n > 0){
            list.add((int)(n % 2));
            n /= 2;
        }
        long[][] dp = new long[list.size()][2];
        dp[0][list.get(0)]++;
        for(int i = 1 ; i < list.size() ; i++){
            if(list.get(i) == 0){
                dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
            }else{
                dp[i][1] = dp[i - 1][0] + dp[i - 1][1];
                for(int j = i - 1 ; j >= 0 ; j--){
                    dp[i][0] += dp[j][0];
                    if(list.get(j) == 1){
                        break;
                    }
                }
            }
        }
        return dp[dp.length - 1][0] + dp[dp.length - 1][1];
    }
}

发表于 2021-09-05 18:57:28 回复(0)