Skip to main content

Depth-first-search

As discussed in the previous posts about the breadth-first-search (bfs), the Depth-first-search (dfs) is another common brute-force searching algorithm. In the dfs, we start with an initial condition for one route, then gradually reach the end of one route; then we repeat the searching on the second route, the third route, ...

Therefore, we can make the following summary:

1. a dfs is one kind of recursion. When search from the current step to the next one, we will call the same function again;

2. the end condition (or base case) should be defined;

3. when the same function is called, the parameters should be updated converging to the end conditions;

4. a dfs should cover all the possible routes;

One possible optimization could be memoization, to record the result once a route is finished; then if we have the change to meet with the same route again in the searching, we could use the saved results directly without reaching the end. In short this method is usually called as dfs + memo, which is in general equivalent to dynamic programming (dp).


Question List


Upper Layer  

Comments

Post a Comment

Popular posts from this blog

Dynamic Programming - Easy Level - Question 1

Dynamic Programming - Easy Level - Question 1 Leetcode 1646  Get Maximum in Generated Array You are given an integer n. An array nums of length n + 1 is generated in the following way: nums[0] = 0 nums[1] = 1 nums[2 * i] = nums[i] when 2 <= 2 * i <= n nums[2 * i + 1] = nums[i] + nums[i + 1] when 2 <= 2 * i + 1 <= n Return the maximum integer in the array nums​​​. Constraints: 0 <= n <= 100 Analysis: This question is quick straightforward: the state and transitional formula are given; the initialization is also given. So we can just ready the code to iterate all the states and find the maximum. See the code below: class Solution { public: int getMaximumGenerated(int n) { int res = 0; if(n<2) return n; vector<int> f(n+1, 0); f[1] = 1; for(int i=2; i<=n; ++i) { if(i&1) f[i] = f[i/2] + f[i/2+1]; else f[i] = f[i/2]; // cout<<i<<" "<<f[i]<<endl; ...
Post a Comment
Read more

Binary Search - Example

Binary Search - Example Leetcode 35  Search Insert Position Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You must write an algorithm with O(log n) runtime complexity. Constraints: 1 <= nums.length <= 10^4 -10^4 <= nums[i] <= 10^4 nums contains distinct values sorted in ascending order. -10^4 <= target <= 10^4 Analysis: The array is sorted, so we just need to run a routine binary search. Make a guest first, then based on the guessed result, we can adjust the search range. See the code below: class Solution { public: int searchInsert(vector<int>& nums, int target) { int left = 0, right = nums.size(); while(left < right) { int mid = left + (right - left) / 2; if(nums[mid] < target) left = mid + 1; else right = mid; } return left; } }; If you know t...
Post a Comment
Read more