There are n squares arranged in a row. Paint each square with three colors of red (Red), pink (Pink) and green (Green). Each square is painted with one color. Any adjacent squares are required. Cannot be of the same color, and the first and last squares are also of different colors. Seek all the painting methods that meet the requirements
1. Recursive algorithm
We don’t care how to paint the first to third grid, we first consider the second to last grid, which is How to color the n-1th grid?
According to the meaning of the question,
A. If the color of this square is different from the color of the first square, then there is only one choice for the nth square (because the beginning and the end The two grids are also of different colors), so the painting method for n-1 squares before is paint(n-1), and the total number of painting methods for n squares is paint(n-1)*1; The nth square and the previous square are divided into two parts)
B. If the color of this square is the same as the color of the first square, then there are 2 choices for the nth square , So the coloring method of the previous n-1 squares is paint(n-2) (why n-2? Because the premise is-“The color of the n-1 square has been compared with the first square The colors are the same, what color is the first one, and what color is the n-1th square”, so the color of the n-1 square does not need to be considered, so the parameter passed in the function is n-2). Therefore, in this case, the total number of coloring methods for n squares is 2*paint(n-2).
The above A and B are the classification of the way of thinking. To put it bluntly, it is the classification discussion thought to be mastered in the junior high school mathematics (the last question of the high school entrance examination) — “If you want to solve the right problem, this problem All cases must be listed”, not the mutually exclusive case of if or else in our C language.
To sum up, the expression to solve the coloring problem is: total number of methods=paint(n-1)*1+2*paint(n-2)
int paint(int n)
{
if (n == 1)
return 3;
else if (n == 2 || n == 3)
return 6;
else
return paint(n-1) + 2 * paint(n-2);
//n-1 grid is different from the first coloring ( paint(n-1)) n-1 grid is painted the same as the first grid paint(n-2)*2
}
2, dynamic programming
#include
using namespace std;
int main()
{
int n;
long long dp[51];
dp[0] = 0;
dp[1] = 3;
dp[2] = 6;
dp[3] = 6;
for (int i = 4; i <= 50; i++)
{
dp[i] = dp[i-1] + 2< /span> * dp[i-2];
}
cin >> n;
cout << dp[n];
return 0;
}
int paint(int n)
{
if (n == 1)
return 3;
else if (n == 2 || n == 3)
return 6;
else
return paint(n-1) + 2 * paint(n-2);
//n-1 grid is different from the first coloring ( paint(n-1)) n-1 grid is painted the same as the first grid paint(n-2)*2
}
#include
using namespace std;
int main()
{
int n;
long long dp[51];
dp[0] = 0;
dp[1] = 3;
dp[2] = 6;
dp[3] = 6;
for (int i = 4; i <= 50; i++)
{
dp[i] = dp[i-1] + 2< /span> * dp[i-2];
}
cin >> n;
cout << dp[n];
return 0;
}