【美團】2017美團點評（可重複背包換零錢）

大富翁遊戲，玩家根據骰子的點數決定走的步數，即骰子點數為1時可以走一步，點數為2時可以走兩步，點數為n時可以走n步。求玩家走到第n步（n<=骰子最大點數且是方法的唯一入參）時，總共有多少種投骰子的方法。

找到規律了，每次都2的n-1次方

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int step=s.nextInt();
        System.out.println(dafuweng(step));
 
    }
    public static int dafuweng(int n){
        int sum=1;
        for(int i=1;i<n;i++){
            sum=sum*2;
        }
        return sum;
    }
 
}
           

給你六種面額 1、5、10、20、50、100 元的紙币，假設每種币值的數量都足夠多，編寫程式求組成N元（N為0~10000的非負整數）的不同組合的個數。

又是動态規劃，繼續學習，最後的輸出很大int裝不下，要用long

import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int sum = s.nextInt();
		System.out.print(money(sum));

	}
	public static long money(int sum) {
		long[] dp = new long[sum + 1];
		int[] coins = new int[] { 1, 5, 10, 20, 50, 100 };
		// 先都指派成1
		for (int i = 0; i < dp.length; i++) {
			dp[i] = 1;
		}
		// 從5元開始，dp[5]=dp[5]+dp[5-5];
		for (int i = 1; i < coins.length; i++) {
			for (int j = coins[i]; j < dp.length; j++) {
				dp[j] = dp[j] + dp[j - coins[i]];
			}
		}
		return dp[sum];
	}
	

}
           

給定一組非負整數組成的數組h，代表一組柱狀圖的高度，其中每個柱子的寬度都為1。 在這組柱狀圖中找到能組成的最大矩形的面積（如圖所示）。 入參h為一個整型數組，代表每個柱子的高度，傳回面積的值。

import java.util.Scanner;

public class HeChangTuan {

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);

		int num = s.nextInt();
		int[] arr = new int[num];
		for (int i = 0; i < num; i++) {
			arr[i] = s.nextInt();
		}
		System.out.println(area(arr));


	}

	public static int area(int[] arr) {
		int area = 0;
		for (int i = 0; i < arr.length; i++) {
			int minheight = arr[i];
			for (int j = i + 1; j < arr.length; j++) {
				// 找i後的最小高度
				minheight = Math.min(minheight, arr[j]);
				area = Math.max(area, (j - i + 1) * minheight);
			}
		}
		return area;
	}

}