749. 約翰的後花園

從實體學到計算機，再到硬體，再到人工智能！

藍橋杯備賽 （LintCode上刷的第一題）

準備藍橋杯大賽已經有很長一段時間了。一直在努力的學習算法，不過之前都是看别人的思路和代碼，從來沒有自己獨自一個人從頭到尾的做完一道題。是以即使今天花了三個小時，做完了這道難度系數最簡單的動态規劃的題目。仍然仍然非常非常有成就感！！！第一步的跨越是最難的，也是最有成就感的！！！

問題描述

約翰想在他家後面的空地上建一個後花園，現在有兩種磚，一種3 dm的高度，7 dm的高度。約翰想圍成x dm的牆。如果約翰能做到，輸出YES，否則輸出NO。

樣例輸出

1. 給出 x = 10，傳回YES。

   解釋：

   x = 3 + 7 : 即需要1匹3 dm高度的磚和1匹7 dm 高度的磚。

2. 給出 x = 5，傳回 NO。

   解釋：

   不能用高度為3 dm的磚和高度為7 dm的磚砌成 5 dm的牆。

3. 給出 x = 13，傳回YES。

   解釋：

   x = 2 * 3 + 7 : 即需要2匹3 dm高度的磚和1匹7 dm 高度的磚。

問題分析

說實話，作為初學者，也不怎麼能看出什麼題采用什麼樣的方法。由于此時狂刷動态規劃的算法，是以現在進入了動态規劃系列問題的刷題階段。我在做這道題的時候，參考了換硬币，換紙币這類相似的題目。整個過程下來，三個小時，流程邏輯思路都很清楚了！

因為借鑒以上兩個題目，是以建立邏輯數組dp[i][aim]表示能否采用i種磚砌成高度為aim的牆。

java實作代碼

package DP;

import java.util.Scanner;

public class JohnGarden1110 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 輸入牆的高度
		int aim = sc.nextInt();

		// 一維數組儲存磚的高度
		int[] brick = new int[2];
		brick[0] = 3;
		brick[1] = 7;
		// dp[i][j]表示用i種磚砌成j高度時一共需要用多少塊磚
		int[][] dp = new int[2][aim + 1];

		// 當隻采用3分米的磚時，隻能組成3的倍數的高度
		for (int i = 0; i * brick[0] <= aim; i++) {
			dp[0][i * brick[0]] = 1;
		}

		if (aim >= 3 && aim <= 1000) {
			// 周遊每一個小于等于aim的值
			for (int j = 3; j < aim; j = j + 3) {
				// 當采用k塊7分米的磚時，對k的值從0開始周遊
				for (int k = 1; j + k * brick[1] <= aim; k++) {
					// 在采用k塊3分米的磚的情況下，再采用7分米的磚，如果能砌成目标高度
					if (j + k * brick[1] == aim) {
//					System.out.println("Yes");
						// 将對應元素值置為1
						dp[1][j + k * brick[1]] = 1;
						System.out.println("j" + j + "  k" + k + " sum" + dp[1][j + k * brick[1]]);
					}
				}
			}
		}

		// 根據dp[1][aim]和dp[0][aim]的值判斷，為1表示可以砌成目标高度，否則不能
		if (dp[1][aim] == 1 || dp[0][aim] == 1) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}

	}
}

           

堅持下來的每一天，都離自己的目标更近一些！有夢想的人在閃閃發亮！