All the DP questions just dwell to these 5 patterns. Using this trick here you can almost solve any problem on dynamic programming! 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] Similar Problems 746. Min Cost Climbing Stairs Easy ...
Comments
Post a Comment