LC: 276. Paint Fence
https://leetcode.com/problems/paint-fence/
276. Paint Fence
You are painting a fence of n posts with k different colors. You must paint the posts following these rules:
Every post must be painted exactly one color.
There cannot be three or more consecutive posts with the same color.
Given the two integers n and k, return the number of ways you can paint the fence.
Example 1:
Input: n = 3, k = 2
Output: 6
Explanation: All the possibilities are shown.
Note that painting all the posts red or all the posts green is invalid because there cannot be three posts in a row with the same color.Example 2:
Input: n = 1, k = 1
Output: 1Example 3:
Input: n = 7, k = 2
Output: 42Constraints:
1 <= n <= 501 <= k <= 105The testcases are generated such that the answer is in the range
[0, 231 - 1]for the givennandk.
The Essence:
Bei dem zweiten Zaun ist die Anzahl der Möglichkeiten, bei welchen die letzten zwei Zäune die gleiche Farbe haben, ist k. Bei dem dritten Zaun ist die Anzahl der Möglichkeiten, bei welchen die letzten zwei Zäune die gleiche Farbe haben, von der Tatsache begrenzt, dass die ersten zwei Zäune unterschiedliche Farben haben müssen. Der entsprechende Anzahl ist dann k*(k-1). Für die Anzahl der Möglichkeiten, wobei die letzten zwei Zäune unterschiedliche sind, gilt die Formel (prev_same+prev_diff)(k-1). Darüber hinaus kann man die Gesamtanzahl für der i-ten Zaun bilden: count[i] = diff[i] + same[i] = (diff[i-1]+same[i-1])(k-1) + diff[i-1]
Details:
Diese linear-rekursive Definition der Zählens ist natürlich von unten nach oben unter Verwendung dynamischer Programmierung lösbar. Die Problemlöser müssen sich mit der dynamischen Programmierung für ein breites Spektrum von Problemen vertraut machen, wie zum Beispiel dieses diskrete Mathematik-Problem und Graphtraversierung-Probleme.Diese linear-rekursive Definition der Zählens ist natürlich von unten nach oben unter Verwendung dynamischer Programmierung lösbar. Die Problemlöser müssen sich mit der dynamischen Programmierung für ein breites Spektrum von Problemen vertraut machen, wie zum Beispiel dieses diskrete Mathematik-Problem und Graphtraversierung-Probleme.
Solution(s) and Further Explanation:
Default Code:
Last updated