DSA GRIND #12

DSA GRIND #12

 by Ashur Baroutta

  

      This weeks work involved climbing into the world of dynamic programming. Its something sometimes done without realization but for those unfamiliar dynamic programming is an algorithmic method of solving optimization problems by breaking the problem down into simpler subproblems. The idea is if we have the optimal solution to all of the subproblems we will have achieved the optimal solution for the overarching problem. 

     So the problem is going to be a 1-dimensional Dynamic programming problem. It states "You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top".

    I started by initializing 3 variables (a,b,c). I set a,b equal to 1. I then setup a for loop with the exit condition of n-1. With each iteration of our loop, in order to make sure i had the accurate and most optimal answer for each distinct way to get to the top, I set c = a + b, a = b, and b = c. We are then tracking specific step on the stairs and the amount of ways to get to the top. 

    After working through the problem, I think the biggest takeaway for me is that dynamic programming has a value in breaking problems down into multiple steps that I can apply to future problems. Also and most importantly, this is a skill I haven't consciously practiced too much so if the intro problems are giving me a headache, I definitely need to work at this more. The submission is as follows : 

 

Comments

Post a Comment

Popular posts from this blog

IP #6 : Reversing an Integer

Image
 Reversing an Integer by Ashur Baroutta     The focus of this submission will be on reversing a given integer passed into our function. Our problem statement is as follows "Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 -1], then return 0." Seems simple, though was actually a little odd. My initial reaction is to convert the integer to a string and then just reverse each character. Though in a way that feels like cheating as I don't think that solution is in the spirit of the assignment,  and it takes more resources to complete.      Pivoting my attention to a mathematical solution made the problem a lot more fun. Say our first example for x is 123. The way we attack it is to setup variables to track the reversed total and to track the remainder of a given iteration, we also create a loop iterating through while x does not equal 0.  The ...
Read more

DSA GRIND #9

Image
 INVERTING A BINARY TREE - AB  This weeks problem is similar to our earlier work on reversing a linked list data structure, but in this instance we're going to be inverting a binary tree. The following picture shows an example of what that means. Like our earlier work, I went about doing this recursively as well. So kept making calls back to the function within itself as we went about inverting the data structure node for node. The results/code is as follows.  The code was solid, though the memory management was pretty lacking, its resource intensive holding the same calls within the stack for execution. 
Read more