CHFOP-Editorial

dp
dshahid380_
easy
encoding
enma2019

#1

PROBLEM LINK:

Practice

Contest

Author: Md Shahid

Tester: Md Shahid

Editorialist: Md Shahid

DIFFICULTY:

Easy

PREREQUISITES:

Array

PROBLEM:

Given a matrix P, each element of P denotes power of each individual. You need to find the optimal path for Chef so that Chef can escape from the jail.

EXPLANATION:

This problem is a type of dynamic programming in which you need to find an optimal path so that Chef can escape from the jail. In this problem Chef can enter into three rooms from current room if exist room(i+1, j), room(i, j+1) and room(i+1, j+1) where room(i, j) is the current location of the Chef. You first need to evaluate the path where sum of the power of soldiers are minimum, then compare this with Chef power if the power of Chef is less than the sum then Chef can not escape from the jail else Chef can escape from the jail. To calculate the minimum power path, you need to think recursively.
Start from the destination, if you destination is room(x, y). To reach at room(x, y) you can come from room(x-1, y), room(x, y-1) and room(x-1, y-1).
So the total power will be
minCost(m, n) = min (minCost(m-1, n-1), minCost(m-1, n), minCost(m, n-1)) + cost[m][n]
You need to iterate in a loop to find the total minimum power sum at destination, then you can compare the sum with Chef’s power.

AUTHOR’S AND EDITORIALIST’S SOLUTIONS:

Author’s and editorialist’s solution can be found here.