Breadth first search (BFS) can be found at ？？？？

The previous understanding of breadth-first search has been limited to hierarchical traversal. Recently, it has been discovered that you can do some things to find the shortest path. Here are two problems to explore.

The first one is to minimize the number of perfect squares that make up the sum. Be reasonable according to my previous understanding, this problem should be DP routine, yes, can be done with DP. But now you can do BFS, and BFS is good for this kind of shortest path, because it’s going layer by layer. Refer to the summary here

The BFS routine is a queue, traversing one layer at a time. There is then a $UESD array that records the nodes visited. So this problem can be viewed as starting with the number n, taking several square steps at a time, and asking the minimum number of final steps to get to 0. Borrow a picture for easy understanding:The gray nodes are the ones that can be skipped, because if one of the preceding nodes reaches zero, then the following nodes don’t need to be counted.

class Solution { /** * @param Integer $n * @return Integer */ function numSquares($n) { $step = 0; $queue = new SplQueue(); $queue->enqueue($n); $used = array_fill(0, $n + 1, 0); $used[$n] = 1; while (! $queue->isEmpty()) { $size = count($queue); $step++; for ($i = 0; $i < $size; $i++) { $top = $queue->dequeue(); for ($j = 1; $top - $j * $j >= 0; $j++) { $cur = $j * $j; $next = $top - $cur; if ($next == 0) { return $step; } if ($next < 0) { continue; } if ($used[$next] == 0) { $used[$next] = 1; $queue->enqueue($next); } } } } } }Copy the code

In fact, after understanding the above diagram and code, it is completely OK to look at the following problem, same idea.The classic change, before, can only think of using DP, now, think about it, is it the same as the above problem. Given an amount, ask for the minimum number of coins needed to make up the amount given some choices each time. As with the code above, the difference is that the number to choose is different each time.

Class Solution {/** * @param Integer[] $coins * @param Integer $amount * @return Integer coinChange($coins, $amount) { if ($amount == 0) { return 0; } $queue = new Splqueue(); $queue->enqueue(0); $used = array_fill(0, $amount + 1, 0); $step = 0; while (! $queue->isEmpty()) { $step++; $size = count($queue); for ($i = 0; $i < $size; $i++) { $cur = $queue->dequeue(); foreach ($coins as $coin) { if ($cur + $coin == $amount) { return $step; } if ($cur + $coin < $amount && ! $used[$coin + $cur]) { $used[$coin + $cur] = 1; $queue->enqueue($cur + $coin); } } } } return -1; }}Copy the code

That’s all for today.