DenCT/test-storage / DSA Notes /Dynamic Programming Notes.md
DenCT's picture
|
download
raw
1.39 kB
metadata
tags:
  - notes
  - dynamic-programming
  - patterns

Patterns

  1. [[#Minimum (Maximum) Path to Reach a Target]]
  2. [[#Distinct Ways]]
  3. [[#Merging Intervals]]
  4. [[#DP on Strings]]
  5. [[#Decision Making]]

Minimum (Maximum) Path to Reach a Target

Problem list: https://leetcode.com/problem-list/55ac4kuc/ Generate problem statement for this pattern

Statement

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

Approach

[!info] 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.

Top-Down

for (int j = 0; j < ways.size(); ++j) {
    result = min(result, topDown(target - ways[j]) + cost/ path / sum);
}
return memo[/*state parameters*/] = result;

Bottom-Up

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

Distinct Ways

Merging Intervals

DP on Strings

Decision Making

Xet Storage Details

Size:
1.39 kB
·
Xet hash:
674e1ddae6bcb4e07c0b1e0e00258e36e9a100a43a3cea174bbe4fe35198fd45

Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.