1
00:00:00,280 --> 00:00:02,320
Hey there and welcome back.

2
00:00:02,320 --> 00:00:04,810
So we have this problem over here.

3
00:00:04,810 --> 00:00:11,920
And we have also discussed the 2D Depee table that we will use for the bottom up or tabulation approach.

4
00:00:11,920 --> 00:00:18,610
Now let's just go ahead and fill this table and have a dry run of the tabulation or bottom up approach

5
00:00:18,610 --> 00:00:20,320
for solving the list question.

6
00:00:20,320 --> 00:00:25,090
We have discussed that these cells over here represent the initial condition.

7
00:00:25,090 --> 00:00:27,880
So let's just fill this up with zeros.

8
00:00:28,760 --> 00:00:32,390
Now let's start filling this cell over here.

9
00:00:32,480 --> 00:00:40,910
Now, this cell has a curve value of two and a prev value of two minus one, which is equal to one.

10
00:00:40,910 --> 00:00:44,450
So cur is equal to two and prev is equal to one.

11
00:00:44,450 --> 00:00:51,710
Now if this represents the array which is given to us, notice that index two is this value over here.

12
00:00:51,710 --> 00:00:53,540
And that's what is given over here.

13
00:00:53,540 --> 00:00:55,940
So we know that cur is equal to two.

14
00:00:55,970 --> 00:01:04,370
Which means that we can consider elements starting at index two and going forward depending on the input

15
00:01:04,370 --> 00:01:04,790
array.

16
00:01:04,940 --> 00:01:13,760
Now we have to go ahead and calculate the exclude value and the include value for this particular subproblem.

17
00:01:13,760 --> 00:01:20,180
And then the bigger value among these two will help us determine what value to fill over here.

18
00:01:20,180 --> 00:01:24,320
So first let's discuss the exclude value that we can get.

19
00:01:24,320 --> 00:01:28,040
Now excluding means we don't include this element.

20
00:01:28,040 --> 00:01:31,940
And we consider only the remaining elements over here.

21
00:01:31,940 --> 00:01:34,790
So that's the meaning of exclude right.

22
00:01:34,790 --> 00:01:36,890
So we don't include this element.

23
00:01:36,890 --> 00:01:41,510
And we consider the remaining elements now in the DP table.

24
00:01:41,510 --> 00:01:42,890
What would that be.

25
00:01:42,890 --> 00:01:50,390
So notice that in the DP table over here the exclude value would be dp at cur plus one.

26
00:01:50,570 --> 00:01:53,870
Because when we do cur plus one we are moving over here.

27
00:01:53,870 --> 00:01:57,200
And that means that we can only consider these elements.

28
00:01:57,200 --> 00:01:59,180
So DP at cur plus one.

29
00:01:59,180 --> 00:02:00,890
So that's the row value.

30
00:02:00,890 --> 00:02:07,640
And then over here, because we have not included the value prev stays as it is.

31
00:02:07,640 --> 00:02:09,950
So we have prev itself over here.

32
00:02:09,950 --> 00:02:14,810
But then whenever we fill this to the DP table remember we discussed.

33
00:02:14,840 --> 00:02:21,800
We have to offset this by one because prev is equal to one is column two in the DP table.

34
00:02:21,800 --> 00:02:23,900
So that's why we have to do plus one.

35
00:02:23,900 --> 00:02:29,180
So exclude is given by DP at cur plus one prev plus one.

36
00:02:29,180 --> 00:02:31,670
So we have the exclude value over here.

37
00:02:31,670 --> 00:02:38,090
So dp at cur plus one pref plus one is equal to this value over here which is zero itself.

38
00:02:38,090 --> 00:02:44,330
And we have this value over here because we have filled the initial conditions in the DP table.

39
00:02:44,330 --> 00:02:47,330
So this is the value of exclude.

40
00:02:47,330 --> 00:02:55,730
Remember previously when we wrote the recursive approach for this question exclude was said to be list

41
00:02:55,760 --> 00:02:57,500
of cur plus one prev.

42
00:02:57,500 --> 00:02:59,870
And that's the same thing that we're doing over here.

43
00:02:59,870 --> 00:03:07,100
Again, notice the benefit or the advantage of first writing the recursive solution and then coming

44
00:03:07,100 --> 00:03:09,620
to the bottom up or tabulation approach.

45
00:03:09,620 --> 00:03:11,210
So this is the same thing.

46
00:03:11,210 --> 00:03:17,570
Just we have plus one over here because we have to offset the value of prev while filling it to the

47
00:03:17,570 --> 00:03:18,380
DP table.

48
00:03:18,380 --> 00:03:23,300
So we have got exclude to be equal to DP at cur plus one prep plus one.

49
00:03:23,300 --> 00:03:25,940
And that's in this case equal to zero.

50
00:03:26,030 --> 00:03:30,050
Now let's go ahead and calculate the value for include.

51
00:03:30,050 --> 00:03:38,840
So include is possible only if the value at index cur is greater than the value at index prev.

52
00:03:38,840 --> 00:03:41,480
So over here prev is equal to one.

53
00:03:41,480 --> 00:03:46,220
So the value at this index is equal to two and cur is equal to two.

54
00:03:46,220 --> 00:03:49,100
And the value at index two is equal to three.

55
00:03:49,100 --> 00:03:51,530
Notice that three is greater than two.

56
00:03:51,530 --> 00:03:54,020
And therefore we are able to include.

57
00:03:54,020 --> 00:03:58,250
So include is going to be equal to one plus.

58
00:03:58,430 --> 00:04:02,720
And then you have to move to the next element in the input array.

59
00:04:02,720 --> 00:04:07,640
So you have to do dp at cur plus one because you included the element at index cur.

60
00:04:07,640 --> 00:04:11,120
And then we only consider elements to the right of Cur.

61
00:04:11,120 --> 00:04:13,760
So that's why we have DP at cur plus one over here.

62
00:04:13,760 --> 00:04:17,570
So we start with elements at index cur plus one.

63
00:04:17,570 --> 00:04:21,170
And notice that prev also has changed.

64
00:04:21,170 --> 00:04:27,890
Prev has to be set to cur because that's the latest element that was included to the subsequence.

65
00:04:27,890 --> 00:04:29,780
And that's why we have cur over here.

66
00:04:29,780 --> 00:04:36,590
And then we have plus one because we have to offset the value of prev before adding it to the DP table.

67
00:04:36,590 --> 00:04:40,190
Notice prev one was added in column two.

68
00:04:40,190 --> 00:04:44,780
So prev equal to cur will be added in column cur plus one.

69
00:04:44,780 --> 00:04:47,420
And that's why we have plus one over here.

70
00:04:47,420 --> 00:04:53,630
So include is going to equal to one plus dp at cur plus one cur plus one.

71
00:04:53,630 --> 00:04:57,920
So we have discussed that we have cur over here because prev is equal to cur.

72
00:04:57,920 --> 00:05:02,570
And then we have plus one over here because we have to offset the value by one.

73
00:05:02,570 --> 00:05:07,010
Now in the table over here where is dp at cur plus one.

74
00:05:07,010 --> 00:05:07,880
Cur plus one.

75
00:05:07,880 --> 00:05:09,950
So over here cur was equal to two.

76
00:05:09,980 --> 00:05:12,170
So cur plus one is equal to three.

77
00:05:12,170 --> 00:05:18,620
So this is dp at three three which is this cell over here which has the value zero.

78
00:05:19,460 --> 00:05:24,860
So include is equal to one plus zero which is equal to one.

79
00:05:24,860 --> 00:05:30,380
So exclude is equal to zero and include is equal to one plus zero, which is one.

80
00:05:30,380 --> 00:05:33,500
And the greater value between 0 and 1 is one.

81
00:05:33,500 --> 00:05:36,590
And therefore we can fill the value one over here.

82
00:05:36,590 --> 00:05:39,020
So we are done with this sub problem.

83
00:05:39,020 --> 00:05:40,370
Now let's proceed.

84
00:05:40,370 --> 00:05:46,730
We come over here where cr is equal to two and prev is equal to zero.

85
00:05:47,750 --> 00:05:51,890
So again we have to calculate exclude and include.

86
00:05:51,890 --> 00:05:55,820
Exclude will be DP at curve plus one which is three.

87
00:05:55,970 --> 00:05:57,980
And you have pref plus one.

88
00:05:57,980 --> 00:05:59,660
So zero plus one is one.

89
00:05:59,660 --> 00:06:01,670
So this is the exclude value.

90
00:06:03,760 --> 00:06:08,500
And include will be one plus DP at car plus one, which is three.

91
00:06:08,500 --> 00:06:10,960
And again you have car plus one which is three.

92
00:06:10,960 --> 00:06:18,190
And we are able to include because the value at index two, which is three, is greater than the value

93
00:06:18,190 --> 00:06:20,020
at index zero, which is one.

94
00:06:20,020 --> 00:06:26,620
So three is greater than one because of which we can include and therefore include is one plus dp at

95
00:06:26,620 --> 00:06:27,520
three three.

96
00:06:27,520 --> 00:06:34,090
So exclude which is DP at three one is this value over here which is zero.

97
00:06:34,090 --> 00:06:38,320
And then dp at three three is also zero and one plus zero is one.

98
00:06:38,320 --> 00:06:41,260
So this value is one and this is zero.

99
00:06:41,260 --> 00:06:44,620
And the greater value between these two is equal to one.

100
00:06:44,620 --> 00:06:48,070
And therefore we can fill the value one over here.

101
00:06:48,820 --> 00:06:56,140
Now let's proceed to the next cell and we have car is equal to two and prev is equal to minus one.

102
00:06:57,550 --> 00:07:03,280
And then again exclude is DPR Korea plus one plus one which is DPR three zero.

103
00:07:03,280 --> 00:07:07,510
And we are able to include because nothing has been included so far.

104
00:07:07,510 --> 00:07:13,840
So we can include and when we include include becomes one plus DPR three three.

105
00:07:13,840 --> 00:07:14,260
Right.

106
00:07:14,260 --> 00:07:15,580
Because car is two.

107
00:07:15,610 --> 00:07:17,320
So car plus one is three.

108
00:07:17,320 --> 00:07:19,690
And then over here also car is two.

109
00:07:19,690 --> 00:07:22,420
And we have to do car plus one for the offset.

110
00:07:22,420 --> 00:07:23,650
So this is also three.

111
00:07:23,650 --> 00:07:29,980
So this value over here becomes one and dp at three zero is zero.

112
00:07:29,980 --> 00:07:34,840
And the greater value between these two is one because of which we can fill one over here.

113
00:07:34,840 --> 00:07:36,790
So we are done with these values.

114
00:07:36,790 --> 00:07:39,070
Now let's come to the next cell.

115
00:07:39,070 --> 00:07:42,370
Now the next cell to be filled is this cell over here.

116
00:07:42,370 --> 00:07:46,270
We don't fill this cell because prev over here is equal to car.

117
00:07:46,270 --> 00:07:49,150
But prev we know has to be less than car.

118
00:07:49,150 --> 00:07:55,030
So we come to this cell over here and we have car is equal to one and prev is equal to zero.

119
00:07:55,030 --> 00:08:02,110
And again you find exclude which is depee at two one and include which is one plus dp at two two.

120
00:08:02,110 --> 00:08:08,350
And you are able to include because the value at index one, which is two is greater than the value

121
00:08:08,350 --> 00:08:09,910
at index zero which is one.

122
00:08:09,910 --> 00:08:13,120
So two is greater than one, because of which we can include.

123
00:08:13,120 --> 00:08:17,410
And then we find exclude over here and include over here.

124
00:08:17,410 --> 00:08:19,090
Now DP two one.

125
00:08:19,090 --> 00:08:20,830
That's this value over here.

126
00:08:20,830 --> 00:08:22,570
So exclude is one.

127
00:08:22,570 --> 00:08:24,280
And then DP two two.

128
00:08:24,700 --> 00:08:26,170
That's this value over here.

129
00:08:26,170 --> 00:08:26,800
That's one.

130
00:08:26,800 --> 00:08:29,290
So include is one plus one which is two.

131
00:08:29,290 --> 00:08:31,300
And exclude is equal to one.

132
00:08:31,300 --> 00:08:33,820
And the greater value between these two is two.

133
00:08:33,820 --> 00:08:36,130
And that's why we fill two over here.

134
00:08:36,160 --> 00:08:41,230
Now in a similar manner we come to the next cell and we fill two also over here.

135
00:08:41,230 --> 00:08:42,820
And then we come over here.

136
00:08:42,820 --> 00:08:52,720
When we come over here we have car is equal to zero and prev is equal to minus one and exclude is this

137
00:08:52,720 --> 00:08:55,600
value over here which is two dp at.

138
00:08:56,360 --> 00:08:58,280
Car plus one prev plus one.

139
00:08:58,280 --> 00:08:59,540
That's exclude right.

140
00:08:59,540 --> 00:09:05,000
So prev plus one is zero and car plus one is one.

141
00:09:05,000 --> 00:09:06,590
So DP at one zero.

142
00:09:06,620 --> 00:09:08,930
That's this value over here which is two.

143
00:09:08,960 --> 00:09:11,690
So exclude is two and include.

144
00:09:12,920 --> 00:09:17,570
Will be one plus DP at curve plus one and curve is zero.

145
00:09:17,570 --> 00:09:18,920
So curve plus one is one.

146
00:09:18,920 --> 00:09:20,870
And over here also you have one.

147
00:09:20,870 --> 00:09:23,420
So DP at one comma one is this two.

148
00:09:23,420 --> 00:09:27,080
And when you add one to it you get include to be equal to three.

149
00:09:27,080 --> 00:09:32,600
Now the greater value exclude was three, include is exclude was two include is three.

150
00:09:32,600 --> 00:09:35,330
Now the greater between these two is equal to three.

151
00:09:35,330 --> 00:09:37,460
And that's how we fill three over here.

152
00:09:37,460 --> 00:09:39,350
And that gives us the answer.

153
00:09:39,350 --> 00:09:46,190
So the answer is equal to three which is the length of the longest increasing subsequence.

154
00:09:46,190 --> 00:09:53,540
So this is the tabulation approach where we are using a 2D array for solving the Liz question.