招商银行fintec训练营编程题

太过爱你忘了你带给我的痛 2022-05-26 01:29 173阅读 0赞

# 一、货币兑换总数 #

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while (t-- > 0) {
            int N = in.nextInt();
            int K = in.nextInt();
            int[] coins = new int[N];
            for (int i = 0; i < N; i++) {
                coins[i] = in.nextInt();
            }
            int[][] dp = new int[N][K + 1];
            for (int i = 0; i < N; i++) {
                dp[i][0] = 1;
            }
            for (int i = 0; i <= K; i++) {
                if (i % coins[0] == 0) {
                    dp[0][i] = 1;
                }
            }
            for (int i = 1; i < N; i++) {
                for (int j = 0; j <= K; j++) {
                    dp[i][j] = dp[i - 1][j];
                    if (j >= coins[i]) {
                        dp[i][j] += dp[i][j - coins[i]];
                    }
                    dp[i][j] %= 100000007;
                }
            }
            System.out.println(dp[N - 1][K]);
        }
    }

# 二、小牛送草 #

private static int[] dp;
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while (t-- > 0) {
            int N = in.nextInt();
            dp = new int[N];
            int[] values = new int[N];
            for (int i = 0; i < N; i++) {
                values[i] = in.nextInt();
            }
            System.out.println(Math.max(sell(values, 0, N - 2), sell(values, 1, N - 1)));
    
        }
    }
    
    private static int sell(int[] values, int first, int last) {
        if (last - first == 0) return values[first];
        if (last - first == 1) return Math.max(values[first], values[last]);
        dp[first] = values[first];
        dp[first + 1] = values[first + 1];
        dp[first + 2] = values[first] + values[first + 2];
        for (int i = first + 3; i <= last; i++) {
            dp[i] = Math.max(dp[i - 2], dp[i - 3]) + values[i];
        }
        return Math.max(dp[last], dp[last - 1]);
    }

[参考链接][Link 1]

[Link 1]: https://www.nowcoder.com/discuss/76910?type=0&order=0&pos=9&page=1