Name: 動態編程面試題1--尋找加起來是16的數字集。 (Dynamic Programming Interview Question #1 - Find Sets Of Numbers That Add Up To 16)
Uploaded: 2021-01-14T10:29:50.000Z
Duration: 20 min 6 s
Description: 【看影片學英語】數萬部 YouTube 影片，搭配英漢字典即點即查，輕鬆掌握單字發音與用法，長久累積看電影不必再看字幕。

to 不定詞

Hey, everyone, in this video, I'm going to give you a programming Slash quoting into big problem for which you can use dynamic programming.

If you're enough on the air with that, I'm Pro Ming.

I'd recommend my dynamic programming introduction video first.

You're given an array off integers, for example, 246 and 10.

And you're supposed to find substance of this array, which add up to a certain number for example, 16.

So in this case, there are two such substance.

And just to make the problem a little bit simpler, you don't have to actually find the subsets themselves.

You just need to find the number of substance that add up to the given number.

So in this example, your function should take this number 16 as well as disarray on return to because they're too subsets of this array that add up to 16.

Now, when you're given a quoting in to be a problem like this one, the typical first step is to ask some clarifying questions so you might ask as a clarifying question.

Is it possible to have negative numbers here?

We only have policy interests here, so there's no zeroes or negative numbers on.

Actually, doesn't matter too much if it's sorted or not.

So is it possible to have two of the same number?

There no duplicates on what if you're given instead of 16 dero as one of the arguments, Why should we return then?

In that case, you should return one from your function because technically, the empty array or the empty set as up to zero.

So you can't just this set on you return one from your function.

So think about this problem for a second and then come back for a solution.

So if I was given this problem, I would first ask myself, How would I solve this problem on a white board or on paper?

The way I would do that is I would start with an empty set, and I would try under construct all the possible subsets of this array.

So for the right most element, or you can start at the left most element.

But let me start with the right most element for that one.

We need to ask ourselves, Do we want to include it in the subset that we're trying to construct?

If the answer is yes, will have a subset off just one element 10.

And if the answer is no will still have on empty set on, we'll need to do the same thing for the next element.

So if we decide to include six to this subset or add six to this upset, we'll have six and 10 on.

If we decide not to include that in, this one will have to sten and so on.

So, just like that, you'll be able to find all the possible subsets off this entire rate on for each of these subsets.

You could just ask yourself, in theory, does it add up to, for example, 16 and then add up all of those subsets and we have the answer.

And when I see this structure, if I was in the actual interview, I might say Well, since it says it's a tree, it actually looks like a rickerson tree, and so maybe I can solve this problem using the courage in.

Of course, the idea of Rikers on Ace to break down the large problem, the original problem into smaller sub problems that are similar in nature.

Let's call the number of substance that add up to 16 out of the entire E, and that's the answer that we're looking for on this end is actually the sum of two numbers.

On the first such number is the number of subsets that add up to 16 which include 10 on the second sits number.

It's the number of substance that out of 2 16 which do not include 10 and actually this first number.

The number of substance that add up to 16 which include 10 is equivalent to the number of substance that out up to six out of these three elements.

So the substance that out up to six out of these three elements are 24 on dhe, just six, and you can sort of merge each of these subsets with this subset with only 10 and get a subset that as up to 16 we can get two of them.

So we can put to here as the first summer on the second number that the number of subsets that add up to 16 which do not include 10 is equivalent to the number of subsets that add up to 16 out of thes three elements.

Because we don't have this in play anymore.

And there's no such subset that as up to 16 out of these three elements, because if you add all of them up, you'd only have 12 as the total sum.

So you have there right here is the second number.

So in this particular example, he also that we're looking for is and is equal to two past era, which is too.

So what we just did as we broke down the large original problem off finding the number of substance that add up to 16 out of this whole array into two smaller sub problems.

And we can actually keep going like that further down the tree as well.

Just keep breaking down the problems into smaller and smaller problems.

So this is the basic idea off my recursive solution.

But one thing to note here is that you don't really have to create or store these individual substance because we're only interested in the number of subsets that add up to a certain number.

We only need to store the some off each subset.

So the Somme off this upset would be 10 and then the some off the empty subset is, of course, zero on the Somme off.

This one is 16 and the sum of 10 is 10 and so on.

Okay, let's now see what this solution might look like.

In code, I'm defining two functions here counts.

It's and wreck count sets will be our main function.

You'll take the array discovery on the total amount that we're trying to find the substance for, and this is going to return the number of substance that add up to the total amount and then wreck will be our recursive function, so it'll call itself with personally on.

It'll take the given array, the total amount and I as an index, and this is going to return the number of substance that add up to the total amount.

But while considering on Lee the elements up to the next I so if you're given, for example, disarray are on six as the total amount on to as the index, that would be right here.

We're only considering these three elements to find the success that add up to a given amount.

And in that case, your function wreck should return to because they're too such substance to four on six.

And the only thing we need to do in count sets is to return wreck with.

The arguments are a total on our doubt length minus one, because our that length minus one would be the last index officer rate.

In this particular example, that would be three.

Okay, the first thing we need to do in the rec function or the Rikers to function is we need to take care of some base cases.

The 1st 1 to take care of is when total is equal to zero.

In that case, we should return one, because when totally is zero, the only substance that adds up to Dara is the empty substance, and there is only one of them on the second base case to take care of age when total is less than zero.

And if that's the case, there's no subset that as up to zero, so we should just return zero.

Since there are no negative numbers in disarray on def I iss less than there that with me, I is already outside of the saree and since we know that total is neither zero nor less than zero total, here is a positive number and since we don't have any more numbers to create a subset with that add up to hopefully total will just return there on.

If none of these cases are true, will then go to our recursive cases.

The first recursive case that we need to deal with is when total is less than our score buckets I or the lasts item though we're examining.

So, for example, if I is equal to two with the examining this item six would be devalued off our school brackets.

And if the given total here is, let's say, four, there would be no way of finding us upset out of thes three elements that add up to four, which includes the current Item six.

So that means the number of substance that add up to the total amount out of these three elements is equivalent to the number of substance that add up to the tour.

Amount out of these two elements is that to express that will just need to write return wreck or a total I'm minus one.

We'll just need to go to the next item or the item that's left to the current item that we're examining.

Other case we need to deal with is everything else.

So we're examining this item currently on the total that we're looking for is six.

If that's the case, we'll need to deal with two different cases.

The first case is when we don't include a six in the substance that we're trying to construct on.

It's the same as before, so we'll just need to write wreck our total I am minus one on the second case is when we do include this item in the subset that we're trying to construct, and just like I explained before the way you can think about it.

Is this the number of substance that add up to the given total six right here, which include this Number six is equivalent to the number of substance that add up to total minus the current item.

I out of thes two elements on Lee so you can find that with wreck or total minus our score brackets.

字幕列表影片播放

動態編程面試題1--尋找加起來是16的數字集。 (Dynamic Programming Interview Question #1 - Find Sets Of Numbers That Add Up To 16)

sort

entire

potential

equivalent