Minimum Initial Points to Reach Destination | Python3 program to find minimum initial points to reach destination ; dp [ i ] [ j ] represents the minimum initial points player should have so that when starts with cell ( i , j ) successfully reaches the destination cell ( m - 1 , n - 1 ) ; Base case ; Fill last row and last column as base to fill entire table ; fill the table in bottom - up fashion ; Driver code
import math as mt NEW_LINE R = 3 NEW_LINE C = 3 NEW_LINE def minInitialPoints ( points ) : NEW_LINE INDENT dp = [ [ 0 for x in range ( C + 1 ) ] for y in range ( R + 1 ) ] NEW_LINE m , n = R , C NEW_LINE if points [ m - 1 ] [ n - 1 ] > 0 : NEW_LINE INDENT dp [ m - 1 ] [ n - 1 ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT dp [ m - 1 ] [ n - 1 ] = abs ( points [ m - 1 ] [ n - 1 ] ) + 1 NEW_LINE DEDENT for i in range ( m - 2 , - 1 , - 1 ) : NEW_LINE INDENT dp [ i ] [ n - 1 ] = max ( dp [ i + 1 ] [ n - 1 ] - points [ i ] [ n - 1 ] , 1 ) NEW_LINE DEDENT for i in range ( 2 , - 1 , - 1 ) : NEW_LINE INDENT dp [ m - 1 ] [ i ] = max ( dp [ m - 1 ] [ i + 1 ] - points [ m - 1 ] [ i ] , 1 ) NEW_LINE DEDENT for i in range ( m - 2 , - 1 , - 1 ) : NEW_LINE INDENT for j in range ( n - 2 , - 1 , - 1 ) : NEW_LINE INDENT min_points_on_exit = min ( dp [ i + 1 ] [ j ] , dp [ i ] [ j + 1 ] ) NEW_LINE dp [ i ] [ j ] = max ( min_points_on_exit - points [ i ] [ j ] , 1 ) NEW_LINE DEDENT DEDENT return dp [ 0 ] [ 0 ] NEW_LINE DEDENT points = [ [ - 2 , - 3 , 3 ] , [ - 5 , - 10 , 1 ] , [ 10 , 30 , - 5 ] ] NEW_LINE print ( " Minimum ▁ Initial ▁ Points ▁ Required : " , minInitialPoints ( points ) ) NEW_LINE