class Solution {
    // 题目要求o(n)的时间复杂度
    // 题目类型dp
    public int[] productExceptSelf(int[] nums) {
        //除nums[i]之外的所有数的乘积也就是将nums[i]当做1
        // 可以计算这个数左乘积和右乘积
        // 用三个数组分别存储前缀、后缀和乘积
        // 对于元素nums[0]，我们设定初始值left[0] = 1;
        // 对于元素nums[nums.length - 1] 设定初始值right[nums.length - 1] = 1;
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];
        int[] res = new int[n];
        left[0] = 1;right[n - 1] = 1;
        for (int i = 1; i < n; i++) {
            left[i] = left[i-1] * nums[i-1];
        }
        for (int j = n - 2; j >= 0; j--) {
            right[j] = right[j + 1] * nums[j + 1];
        }
        for (int i = 0; i < n; i++) {
            res[i] = left[i] * right[i];
        }
        return res;

    class Solution {
    // 背包问题，完全背包
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1]; // dp[i] 代表组成金额为i的最少硬币数
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] = Math.min(dp[j], dp[j-coins[i]] + 1);
            }
        }
        return dp[amount]== amount+1 ? - 1 : dp[amount];

    }
}}
}