leetcode-go/oj/tencent-2018-spring/SongList.java

import java.util.Scanner;

public class SongList {
    private static final int MOD = 1000000007;

    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            int K = scanner.nextInt();
            int A = scanner.nextInt(), X = scanner.nextInt();
            int B = scanner.nextInt(), Y = scanner.nextInt();
            int[][] dp = new int[X + Y + 1][K + 1];
            dp[0][0] = 1; // !!important
            for (int i = 1; i <= X + Y; i++) {
                for (int j = 0; j <= K; j++) {
                    dp[i][j] = dp[i - 1][j]; // Do not pick current song.
                    int len = X < i ? B : A;
                    if (len <= j) dp[i][j] = (dp[i][j] + dp[i - 1][j - len]) % MOD; // Pick
                }
            }
            System.out.println(dp[X + Y][K]);
        }
    }
}