2 x N 바닥을 채울 수 있는 1x1, 1x2, 2x1 타일의 가능한 조합 수를 계산하는 방법은 무엇입니까?

php 편집자 Xinyi는 모두를 위한 흥미롭고 두뇌를 자극하는 질문에 답할 것입니다. 1x1, 1x2, 2x1 타일의 가능한 조합이 2 x N 바닥을 채울 수 있는 수는 어떻게 계산할 수 있습니까? 이 문제에는 조합수학과 동적 프로그래밍에 대한 지식이 필요하며, 분석과 도출을 통해 간단하고 효과적인 계산 방법을 생각해 낼 수 있습니다. 다음으로, 이 질문에 대한 답을 함께 살펴보겠습니다!

질문 내용

방금 기술 테스트를 했는데 이 작업에 대해 혼란스러워요. 나의 목표는 이 "덮인 바닥" 문제를 해결하는 방법을 이해하는 것입니다. 솔직히 어디서부터 시작해야할지 모르겠습니다.

미션은:

1. 2xn 레이어가 있습니다.
2. 바닥을 채울 수 있는 1x1, 1x2, 2x1 타일이 있습니다.

질문은:

1. solution(1) 예상 출력은 2, 실제 출력은 2입니다.
2. 그러나 solution(2) 예상 출력은 7이고 실제 출력은 3입니다.

현재 해결 방법은 다음과 같습니다.

1. 1x1은 항상 2xn 레이어를 채울 수 있으므로 가능한 방법은 1부터 시작됩니다.
2. 남은 층수 모드 2가 0이면 가능한 길은 1씩 증가합니다.

현재 솔루션의 문제점은 1x2 블록과 2x1 블록을 구분하지 않는다는 것입니다. 따라서 solution(2)의 경우 실제 출력은 7이 아닌 3입니다.

코드

package main

import "fmt"

// Solution is your solution code.
func Solution(n int) int {
    possibleWays := 1

    floorArea := 2 * n
    // Your code starts here.

    for i := floorArea - 1; i >= 0; i-- {
        residualFloorArea := floorArea - i
        fmt.Println(i, residualFloorArea)
        if residualFloorArea%2 == 0 {
            fmt.Println("punch")
            possibleWays += 1
        }
    }

    return possibleWays
}

func main() {
    fmt.Println(Solution(1))
    fmt.Println("next")
    fmt.Println(Solution(2))
}

Solution

좀 더 설명적이고 철저한 시도:

2xn 그리드를 호출하는 방법의 수는 x_n, 2xn+1 그리드를 덮는 방법의 수는 y_n, 2xn+2 그리드를 덮는 방법의 수는 z_n입니다.

기본 사례:

• x_0 = 1, y_0 = 1, z_0 = 2
• x_1 = 2, y_1 = 3, z_1 = 5

유도 단계, n >=2:

으아악

2xn + 2 그리드의 가장 왼쪽 셀을 생각해 보세요. 1x1 타일로 덮여 있으면 나머지는 2xn + 1 그리드이고, 그렇지 않으면 1x2 타일로 덮여 있고 나머지는 2xn 그리드입니다. 그러므로

z_n = x_n + y_n

으아악

2xn + 1 그리드의 가장 왼쪽 셀을 생각해 보세요. 1x1 타일로 덮여 있으면 나머지는 2xn 그리드가 되고, 그렇지 않으면 1x2 타일로 덮여 있으면 나머지는 2x(n- 1) + 1이 됩니다. 그리드. 그러므로

y_n = x_n + y_(n-1)

으아악

2xn 그리드의 왼쪽 상단을 생각해 보세요. 1x1 타일로 덮이면 나머지는 2x(n-1) + 1 그리드가 되고, 1x2 타일로 덮으면 나머지는 2x( n-2) + 2 그리드, 그렇지 않으면 2x1 타일로 덮이고 나머지는 2x(n-1) 그리드가 됩니다. 따라서:

x_n = y_(n-1) + z_(n-2) + x_(n-1)

z_n을 x_n + y_n으로 바꾸면 다음과 같습니다.

• x_n = x_(n-1) + x_(n-2) + y_(n-1) + y_(n-2)
• y_n = x_n + y_(n-1)

이제 각 값을 반복해 보세요.

으아악

슬라이스를 사용하지 않고도 이 작업을 수행할 수 있지만 이해하기가 더 쉽습니다. 놀이터 데모

위 내용은 2 x N 바닥을 채울 수 있는 1x1, 1x2, 2x1 타일의 가능한 조합 수를 계산하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!