The ultimate guide to coding interviews. Developed by FAANG engineers. Boost problem-solving skills with number theory, dynamic programming, and graph theory. Get interview-ready in just a few hours.

Competitive Programming - Crack Your Coding Interview.png

Whether you’re gearing up for online coding challenges, code-a-thons, or interviews, then this course is for you. With this course, you will solidify your problem-solving skills ensuring a swift sail through any problem. 


You will be tasked with solving some of the most frequently asked questions that are brought up in FAANG interviews. You will start with the concepts of Number Theory and Divide and Conquer, and gradually move towards more complex problems like dynamic programming and graph theory.


With each problem you solve, there will be insightful explanations and full implementation details to really hammer home the concepts. By the time you finish this course, you will have the confidence to solve any problem, no matter the difficulty.

Competitive Programming - Crack Your Coding Interview, C++

## Problem statement
We are going to start from the simplest problems based on Grids and move on to more complex grid problems in subsequent lessons. The problem in this lesson tries to solve the following type of question:
> *Finding Minimum-Cost Path in a 2-D Matrix*

The problem statement is:

**Given a cost matrix `cost[][]`, where `cost[i][j]` denotes the cost of visiting cell with coordinates
`(i,j)`, find a min-cost path to reach a cell `(x,y)` from cell `(0,0)` under the condition that you can only
travel one step right or one step down. (Assume that all costs are positive integers)**

## Solution: **Dynamic programming approach**
It is very easy to note that if you reach a position **(i, j)** in the grid, you must have come from one cell
higher, i.e., **(i-1, j)** or from one cell to your left, i.e., **(i, j-1)**. This means that the cost of visiting cell **(i, j)** will come from the following recurrence relation:

**MinCost(i,j) = min{ MinCost(i-1,j), MinCost(i,j-1) } + cost[i][j]**

We now compute the values of the base cases, the topmost row and the leftmost column. For the topmost row, a cell can be reached only from the cell on the left of it. Assuming zero-based index,

  **MinCost(0,j) = MinCost(0,j-1) + Cost[0][j]**

  **MinCost(i,0) = MinCost(i-1,0) + Cost[i][0]**

i.e., **cost of reaching cell (0,j) = Cost of reaching cell (0,j-1) + Cost of visiting cell (0,j)** and  similarly, **cost of
reaching cell (i,0) = Cost of reaching cell (i-1,0) + Cost of visiting cell (i,0)**.

Let's look a the code now.

# Problem statement
We are going to start from the simplest problems based on Grids and move on to more complex grid problems in subsequent lessons. The problem in this lesson tries to solve the following type of question:
> *Finding Minimum-Cost Path in a 2-D Matrix*

The problem statement is:

**Given a cost matrix `cost[][]`, where `cost[i][j]` denotes the cost of visiting cell with coordinates
`(i,j)`, find a min-cost path to reach a cell `(x,y)` from cell `(0,0)` under the condition that you can only
travel one step right or one step down. (Assume that all costs are positive integers)**

# Solution: **Dynamic programming approach**
It is very easy to note that if you reach a position **(i, j)** in the grid, you must have come from one cell
higher, i.e., **(i-1, j)** or from one cell to your left, i.e., **(i, j-1)**. This means that the cost of visiting cell **(i, j)** will come from the following recurrence relation:

**MinCost(i,j) = min{ MinCost(i-1,j), MinCost(i,j-1) } + cost[i][j]**

We now compute the values of the base cases, the topmost row and the leftmost column. For the topmost row, a cell can be reached only from the cell on the left of it. Assuming zero-based index,

  **MinCost(0,j) = MinCost(0,j-1) + Cost[0][j]**

  **MinCost(i,0) = MinCost(i-1,0) + Cost[i][0]**

i.e., **cost of reaching cell (0,j) = Cost of reaching cell (0,j-1) + Cost of visiting cell (0,j)** and  similarly, **cost of
reaching cell (i,0) = Cost of reaching cell (i-1,0) + Cost of visiting cell (i,0)**.

Let's look a the code now.

Learn to solve easy grid-based problems with dynamic programming.

Overview

Number Theory

Number Theory

Divide and Conquer

Greedy Algorithms

Greedy Algorithms

Recursion and Backtracking

Recursion and Backtracking

Dynamic Programming

Graphs

Bonus Lessons

Problems Involving Grids - 1

Problem statement