DP problem solving

The problem I will be solving is Sums in a Triangle .The problem basically asking us to find the maximum sum in a single path from the given triangle and path can be 1st rows number+ next rows number from the same column or current column+1 and then next row and so on.
At a glance the solution that comes in mind is that we'll take the number from first row and then from next row we'll take the number from same column or current column+1 depending on which one is maximum. But this is a greedy approach and if you see the 2nd test case, you'll see that this approach doesn't give us the correct answer. the second test case:

1

1 2

4 1 2

2 3 1 1

Here if we take 1 then if we follow greedy approach and take 2 from 2nd row because that is the maximum between 1 and 2, then from 3rd row we can't take 4. Because the constraints says the path can be the below row and same column or current column+1(that means one place to the right) so, the answer we'll get in this approach is 6 which is wrong.

But if we use bottom up approach we'll get correct answer. In bottom up approach we'll divide the triangle into smaller triangles. And as the name suggest we'll start from the bottom(last row). So, if we draw the the triangle in  row and column:

If we start from row 4 column 1 and row 4 column 2, between these two if we add 3 with 4 we'll get the maximum number, so the answer for row 3 column 1 is 7. And if we follow  same method we'll get answer 4 for row 3 column 2. Calculating all the rows we'll get a triangle like below:

We can see at the 1st row we get the result. In the beginning I've said in bottom up approach we'll divide it in smaller triangle and that's what we did. We took row 4  column 1, row 4 column 2 and row 3 column 1 as a smaller triangle and that gave us the answer for row 3 column 1. And that's how we got the result for other rows also.

Now let's get to the coding part. as we are dealing with rows and columns ,it is obvious that we have to take a 2d array and and take input.

Now let's implement the bottom up approach. What we are doing is we are starting from the last row and checking maximum value of two column of that row till the column number is one less than the row number:

If you notice I'm running the outer loop till 2 , though I've take input from 1. This is because, we are storing the result in a[i-1][j] by adding it with the maximum of a[i][j] and a[i][j+1], if we run loop till 1 when i=1, we'll have  a[0][j] where we don't have any value.  And then in the inner loop we're just checking which one is maximum and adding it with the previous rows number, exactly what we did in the table earlier. And at the end we are printing the number from first row, because that's where we get the result duh! (remember the table ;) ).
The whole code looks like this:

And the reason it is a dp problem  is because we could divide it in sub problem and at the end got result by solving those sub problems.

Recursion

Recursion can be used when you have a big problem that can be divided into smaller sub problems and by solving those sub problems we can  solve the bigger problem. For example, how we find out factorial of, we calculate like this:

                                                           

                             n! = n*(n-1)*(n-2)*...*1

If we see the line above we are multiplying  n*(n-1)*(n-2)*...*1, so if we were finding out (n-1)!.

 How would we write it?

 We would write it like :

                                 (n-1)! = (n-1)*(n-2)*(n-3)*...*1

Now, we can write the first equation n! = n * (n-1)!

Similarly, (n-1)!= (n-1)*(n-2)!

So, finding out factorial of n is dependent on finding out factorial of n-1 and finding factorial of n-1 is dependent on finding out factorial of n-2. That's why we can use recursion here, because here we have  sub problems with same nature but smaller input size.

Now if we see the c++ code for it:

In the code, in main function I have called the function factorial(5). So, main is asking the factorial function for the answer of n!, in the function initially n = 5 then in line 6 it checks if n=0 , as it is not program goes to line 10 and return n*factorial(n-1) that means 5*factorial(4) so, again factorial()

function is called and the is another instance of the factorial function is created which has n=4. After this for n=4 factorial(4) is called and it goes on like this.

By the way I didn't explain why I have written a if condition in the beginning of  the function that is written because in recursion you need a base case and if you don't give a base case after factorial(0) it will call factorial(-1) then factorial(-2) and so on...but as we are making instance of functions, it is occupying some memory and if we keep calling the function we may run out of memory and we will get segmentation fault. The other reason of giving a base case is we want to eventually come up with an answer and we have to make sure recursion stops somewhere,and as we know 0!=1 we are stopping there . 

Now lets go back to the code and see how the function calling is happening :

So, the function is called till n=0 and factorial(0) is called. And the instances of the function that means factorial(5),factorial(4), factorial(3),factorial(2) , factorial(1) is still waiting in line 10 to get the values of  factorial(4), factorial(3),factorial(2) , factorial(1) and  factorial(0). When n becomes 0 the the if condition is satisfied and 1 is returned. Keep that in mind that 1 is returned to factorial(1) and not to main(). So, now factorial(0) = 1 and as we return n*factorial(n-1) that means factorial(1) = 1*factorial(0) = 1*1=1. This 1 is returned to factorial(2) so,factorial(2) = 2*1=2 which is returned to factorial(3) so,factorial(3) = 3*2=6 .

 This 6 is returned to factorial(4) so factorial(4) = 4*factorial(3) = 4*6 = 24. This 24 is returned to factorial(5) so factorial(5) = 5*factorial(4) = 5*24 = 120. Finally 120 is returned to main() function and it is printed. You should run the code and see ;). 

This is how the  code is working. And in the memory these functions are stacked like this:

I hope it helped you understand how recursion works.

Density Independent Pixel

In Android material design first thing that we have to think about is if the app looks as expected on all devices irrespective of the screen size. That's where density independent pixel (or DP) comes into action. Density independent pixel allows us to create assets that appears in an expected way across all devices no matter what is the resolution or density of a target device. Basically, it gives your app the consistent look that you expected.

For example, if you give a the size of a button 20px that may look great in the device that you are testing your app on, but if you run it on a different device it may not look the way you intended it to look. That's because when you set the size on pixel,it is fixed therefor in a small device if  it looks good then in a bigger device it will look really small.

So, I just said that if we give px(pixel) unit, it is fixed but what happens when we give dp (density independent pixel) unit. At runtime the system handles any scaling of the dp units. One dp is equivalent to 1px in a 160dpi(dots per inch) screen, this is the baseline  density.

The conversion equation of px and dp is:

                                                px/dp = dpi/160dpi

If we have a a screen with 213dpi screen then we'll get 1dp equal to 1.3px.

                                               px = dp*(dpi/160dpi) = dp*(213/160 ) = 1.3dp
So, this is what I know about dp. If there's any mistakes feel free to point it out but be kind :) .