Hello! In this lecture, we will cover an algorithm problem to calculate Ichin numbers<\/strong>. An Ichin number is a number made up of 0s and 1s that does not have two consecutive 1s. For example, 3-digit Ichin numbers are 000, 001, 010, 100, 101, 110, which totals to 6.<\/p>\n Given an integer There are two approaches to solve this problem. The first method uses recursion with DFS (Depth-First Search), and the second method uses Dynamic Programming. Let’s take a detailed look at each method.<\/p>\n The recursive method follows these two rules to generate Ichin numbers:<\/p>\n According to these rules, we can write a recursive function to generate Ichin numbers. Here is the implementation:<\/p>\n The above code defines a recursive function When calculating Ichin numbers, using dynamic programming allows for a more efficient solution through memorization. The count of Ichin numbers I(n) can be defined with the following recurrence relation:<\/p>\n The meaning of this equation is as follows:<\/p>\n Now we will implement dynamic programming based on this recurrence relation:<\/p>\n With the above code, the dynamic programming approach to finding Ichin numbers has been efficiently implemented.<\/p>\n The recursive method is easy to understand but may be inefficient for large N values. In contrast, the dynamic programming method uses memory to reuse previous computation results, making it more performant. Generally, it is advisable to use dynamic programming for larger N values.<\/p>\n In this lecture, we discussed the problem of finding Ichin numbers. We learned to calculate Ichin numbers using both recursive and dynamic programming methods. I hope this problem helps you enhance your algorithmic problem-solving skills.<\/p>\n Thank you!<\/p>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"Problem Description<\/h2>\n
N<\/code>, we will solve the problem of finding all N-digit Ichin numbers and outputting their count.<\/p>\nProblem<\/h3>\n
\nInput N and output the count of all N-digit Ichin numbers.\n<\/pre>\n
Example Input<\/h3>\n
\nN = 3\n<\/pre>\n
Example Output<\/h3>\n
\n6\n<\/pre>\n
Approach to the Problem<\/h2>\n
1. Method Using Recursive DFS<\/h3>\n
\n
def count_ichin(N, current_sequence, last_digit):\n if len(current_sequence) == N:\n return 1\n\n count = 0\n if last_digit == 0:\n count += count_ichin(N, current_sequence + '0', 0)\n count += count_ichin(N, current_sequence + '1', 1)\n else:\n count += count_ichin(N, current_sequence + '0', 0)\n\n return count\n\nN = 3\nresult = count_ichin(N, '', 0)\nprint(result)<\/code><\/pre>\ncount_ichin()<\/code> to generate Ichin numbers, passing N and an empty string as initial values. The last digit starts as 0.<\/p>\n2. Method Using Dynamic Programming<\/h3>\n
I(n) = I(n-1) + I(n-2)<\/code><\/pre>\n\n
def find_ichin_count(N):\n if N == 1:\n return 1\n elif N == 2:\n return 1\n\n dp = [0] * (N + 1)\n dp[1] = 1\n dp[2] = 1\n\n for i in range(3, N + 1):\n dp[i] = dp[i - 1] + dp[i - 2]\n\n return dp[N]\n\nN = 3\nresult = find_ichin_count(N)\nprint(result)<\/code><\/pre>\nComparison and Selection<\/h2>\n
Conclusion<\/h2>\n