Dynamic Programming Patters | Pattern 1 | Minimum (Maximum) Path to Reach a Target

Patterns :

Minimum (Maximum) Path to Reach a Target

Distinct Ways

Merging Intervals

DP on Strings

Decision Making

Minimum (Maximum) Path to Reach a Target

Generate problem statement for this pattern

Statement

Given a target find minimum (maximum) cost / path / sum to reach the target.

Approach

Choose minimum (maximum) path among all possible paths before the current state, then add value for the current state.

routes[i] = min(routes[i-1], routes[i-2], ... , routes[i-k]) + cost[i]

Generate optimal solutions for all values in the target and return the value for the target.

for (int i = 1; i <= target; ++i) {
   for (int j = 0; j < ways.size(); ++j) {
       if (ways[j] <= i) {
           dp[i] = min(dp[i], dp[i - ways[j]] + cost / path / sum) ;
       }
   }
}
 
return dp[target]

Sample Problems:

1. Min Cost Climbing Stairs

Solution : 
 for(int i=2;i<n;i++){
            dp[i]=Math.min(dp[i-1],dp[i-2])+ cost[i];
        }
        return Math.min(dp[n-2],dp[n-1]);

https://github.com/siddharthnawani/leetcode/tree/april-30daychallenge-2020/DynamicProgramming/src/com/sid/leetcode

2.  To Do