Dynamic Programming: Basics and a Practical Example

Introduction: Dynamic programming is a problem-solving technique that can seem quite intimidating at first glance. However, once you grasp its fundamentals and see it in action, you'll find it to be a powerful tool in your coding arsenal. In this blog post, we'll demystify the basics of dynamic programming and walk through a practical example. We'll provide you with clear explanations and a complete Python program, so you can understand and apply this essential concept with confidence. Understanding Dynamic Programming: At its core, dynamic programming is all about breaking down a complex problem into smaller, overlapping subproblems. It's a technique used to efficiently solve problems by storing and reusing solutions to these subproblems, rather than recomputing them. This leads to significant improvements in runtime complexity. Example: Fibonacci Sequence with Dynamic Programming Let's start by tackling a classic problem: calculating Fibonacci numbers. The Fibonac...
Post a Comment

Week of Code 36 - Hackerrank

Q-1 Acid Naming
Solution:-
public class Solution {
   public static void main(String[] args) throws Exception{
       
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
       int n = Integer.parseInt(br.readLine());
       
       for(;n-->0;){
           String acid = br.readLine().trim();
           acid =acid.toLowerCase();
           
           if(acid.startsWith("hydro") && acid.endsWith("ic")){
               System.out.println("non-metal acid");
           } else if(acid.endsWith("ic")){
               System.out.println("polyatomic acid");
           } else {
               System.out.println("not an acid");
           }
       }
   }
}



Q-2 Revised Russian Roulette
Solution :-
public class Solution {
   static int[] revisedRussianRoulette(int[] d) {
      
       int result[] = new int[2];
       for(int i = 0 ; i < d.length; i++){
           if(d[i]==1){
               result[1]++;
           }
       }
       
       for(int i = 0 ; i < d.length; i++){
           if(d[i]==1){
               result[0]++;
               d[i] = 0;
               
               if(i<d.length-1){
                   d[i+1] = 0;
               }
           }
       }
       
       return result;
   }
   public static void main(String[] args)throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
       int n = Integer.parseInt(br.readLine());
       
       int[] doors = new int[n];
       String doorstring[] = br.readLine().split(" ");
       
       for(int i = 0; i < n; i++){
           doors[i] = Integer.parseInt(doorstring[i]);
       }
       
       int[] result = revisedRussianRoulette(doors);
       System.out.println(result[0] + " " + result[1]);
   }
}
Q-4 A Race Against Time
Solution :-
Coming soon
For Solution Video

Comments

Post a Comment

Popular posts from this blog

Array Transformation | biweekly-contest-12 | leetcode | Java Solution

Question Source Java Solution: class Solution {     public List<Integer> transformArray(int[] arr) {                  while(true) {             boolean isChanged = false;             int []copy = arr.clone();                          for(int i = 1; i < arr.length-1; i++) {                                 if(arr[i-1] > arr[i] && arr[i+1] > arr[i]) {                      copy[i]++;                     isChanged = true;                 }else if(arr[i-1] < arr[i] && arr[i+1] < arr[i]) {               ...
Read more

Dynamic Programming: Basics and a Practical Example

Introduction: Dynamic programming is a problem-solving technique that can seem quite intimidating at first glance. However, once you grasp its fundamentals and see it in action, you'll find it to be a powerful tool in your coding arsenal. In this blog post, we'll demystify the basics of dynamic programming and walk through a practical example. We'll provide you with clear explanations and a complete Python program, so you can understand and apply this essential concept with confidence. Understanding Dynamic Programming: At its core, dynamic programming is all about breaking down a complex problem into smaller, overlapping subproblems. It's a technique used to efficiently solve problems by storing and reusing solutions to these subproblems, rather than recomputing them. This leads to significant improvements in runtime complexity. Example: Fibonacci Sequence with Dynamic Programming Let's start by tackling a classic problem: calculating Fibonacci numbers. The Fibonac...
Read more

leetcode | Longest Substring Without Repeating Characters Solution

Source Problem: Given a string, find the length of the  longest substring  without repeating the characters. Example 1: Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Example 2: Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. Example 3: Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring. Solution: class Solution {     public int lengthOfLongestSubstring(String s) {                  Set<Character> subStr = new HashSet<>();         int maxLength = 0;         int j = 0;         for(int i = 0; i < s.length(); i++) {                          if(subStr.contains(s.charAt(i))){ ...
Read more