Frog Jump Problem | Leetcode# 403 | Step by step explanation

In this video of Joey'stech you will learn to solve the frog jump problem using dynamic programming technique. This problem was asked in one of the interviews of Google so watching it and learning it will be good for your interview preparation. I have taken this problem from leetcode in which its serial number is 403. The frog jump problem is an advanced level dynamic programming problem, but, it can be solved without much complexity if you have practiced enough basic DP problems. At the end of this video of my dynamic programming tutorial, I am going to tell you how the solution of this DP problem occurred to me. So, all you have to do is watch this video till the end. ---------------- Problem statement ------------------------- A frog has to cross a river. There are stones lined up in the river by hopping on which the frog can reach across the river. The stones are represented by numbers which indicate their distance from the bank of the river where the frog currently is. The condition which spices up the problem is that if the last jump of the frog is k then the next jump of the frog can be either k-1, k or k+1. So, for example if the frog took the last jump as 2m then he can take the next jump of either jump 1m , 2m or 3m. With distance of stones provided, you need to find out if the frog can cross the river by landing on the last stone. You can assume that the frog is sitting on the first stone which is 0m away from the bank. The problem also states that the first jump the frog will take will be of 1 m. Irrespective of the test cases there will always be a minimum of 2 stones in the river. I am sure this DP problem looks intriguing to you and to take yourself one level in algorithms you should now watch this video. ------------------ Don't forget to watch ---------------------------- Minimum cost of tickets using dynamic programming https://youtu.be/KvMQaC8Dmg0 Coin game winner where every player has 2 choices (DP) https://youtu.be/uXqoNkv_Iv0 Unique paths in a grid with obstacles https://youtu.be/uXOCcM_A5KY Find if N people can vote on 2 machines https://youtu.be/liIlrM57xy4 Partition problem using dynamic programming https://youtu.be/n3LS2p7xoE8