Algorithm: Dynamic Programming Understanding(1)
Dynamic Programming would be nightmare for all coders…
What is Dynamic Programming?
It’s a computer programming technique where an algorithm problem is first broken down into sub-problems, the results are saved, and then the sub-problems are optimized to find the overall solution.
It’s mainly an optimization over plain recursion, wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming.
Trial Model: From left to right
Bag Problem
Let’s start from a very classic dynamic programming (DP) problem – Bag problem
Given 2 arrays with same length: N, represent the item value and item weight separately
then given a integer: bag representing the total weight of item this bag can handle
calculate the max value you can get within this bag.
Plain Recursion
Obviously, this problem cannot be solved within O(N), when you just look at item itself, you cannot know if you should take it or ignore it. this choice is determined by global conditions.
Let’s start from a very naive solution – Plain Recursion
public class BagAlgorithm {
private int[] weights;
private int[] values;
private int maxValue = Integer.MIN_VALUE;
public BagAlgorithm(int[] weights, int values) {
this.weights = weights;
this.values = values;
}
public int getMaxValue(int bag) {
return process(0, bag);
}
// assume the selection of [0..i - 1] is determined,
// the max value we can get from [i.. n]
private int process(int i, int rest) {
if(i == this.weights.length || rest <= 0) {
return 0;
}
int pickCur = this.values[i] + process(i+1, rest - this.weight[i]);
int ignoreCur = process(i + 1, res);
return Math.max(pickCur, ignoreCur);
}
}
Memorized Recursion
We already figured out the most basic way to solve the bag issue. but if we look into the solution, we can find there are some repeated calls with same parameter.
so let’s build a cache for this function so that we can save some time
public class BagAlgo {
// ... previous implemention is similar to above one
private int processWithCache(int i, int rest, int[][] cache) {
if (i >= this.weights.length || rest <= 0) {
return 0;
}
if (cache[i][rest] != 0) {
return cache[i][rest];
}
int pickCur = this.values[i] + processWithCache(i + 1, rest - this.weights[i], cache);
int ignoreCur = processWithCache(i + 1, rest, cache);
int max = Math.max(pickCur, ignoreCur);
cache[i][rest] = max;
return max;
}
}
Dynamic Programming
If we already have the memorized recursion version, we can easily figure out the dependencies between different parameters, which is the key step of Dynamic Programming.
To be more specific, we can know the value of [i, rest] is dependent on [i + 1, rest - weight[i]] & [i+1, rest]
public class BagAlgoDP {
private int processDP(int i, int rest) {
int[][] dp = new int[this.weights.length, rest];
for(int row = dp.length - 2; row >= 0; row--) {
for(int col = dp[0].length - 1; col >= 0; col--) {
dp[row][col] = Math.max(dp[row + 1][col], this.values[row] + dp[row + 1][rest - this.weights[row]]);
}
}
return dp[i][rest];
}
}
Print all sub-sequence
what’s the sub-sequence of a string?
it’s a new string that is formed from the original string by deleting some (or none) of the characters without disturbing the relative positions of the remaining characters.
plain recursion
public class AllSubSeqPrinter {
Set<String> printed = new HashSet<>();
public void print(String origin) {
process(origin.toCharArray(), 0, new StringBuilder());
}
private void process(char[] str, int i, StringBuilder sb) {
if (i == str.length) {
String cur = sb.toString();
if (!printed.contains(cur)) {
sout(cur);
printed.add(cur);
}
return cur;
}
process(str, i + 1, sb.append(str[i]));
process(str, i + 1, sb);
}
}
String Decoder
Given a string of integer, say “111”,
assume 1 -> a, 2 -> b, 11 -> k
return all possible decoding result of given string
plain recursion
public class StringDecoder {
Set<String> res = new HashSet<>();
public void decode(String input) {
char[] cArr = input.toCharArray();
int[] arr = new int[cArr.length];
for(int i = 0; i < cArr.length; i++) {
arr[i] = Integer.valueOf(cArr);
}
process(arr, 0, new StringBuilder());
for(String str: res) {
sout(str);
}
}
private void process(int[] input, int i, StringBuilder sb) {
if (i == input.length) {
String cur = sb.toString();
if (!res.contains(cur)) {
res.add(cur);
}
return;
}
if (input[i] == 0) {
return;
}
char c = 'a' + (input[i] - 1);
process(input, i + 1, sb.append(c));
sb.delete(sb.length() - 1);
if (input[i] == 1 && i + 1 <input.length) {
c = 'a' + 10 + input[i + 1];
process(input, i + 2, sb.append(c));
} else if (input[i] == 2 && i + 1 < input.length) {
if (input[i + 1] >= 0 && input[i + 1] <= 6) {
c = 'a' + 20 + input[i + 1];
process(input, i + 2, sb.append(c));
}
}
}
}
Trial Model: Range
there is another trial model which is from both side to center.
let take following problem as examle
Poker Pick Problem
Given an array representing pokers,
two players can only pick pokers on both end,
assume both players perform the best on each round,
predict who will won
Plain Recursion
public class PokerGame {
private int[] arr;
public void predictWhoWillWon(int[] arr) {
this.arr = arr;
if(foreHand(0, arr.length - 1) > hindHand(0, arr.length - 1)) {
sout("first player will won");
} else {
sout("second player will won");
}
}
private int foreHand(int start, int end) {
if(start == end) {
return this.arr[start];
}
return Math.max(
arr[start] + hindHand(start + 1, end);
arr[end] + hindHand(start, end + 1);
);
}
private int hindHand(int start, int end) {
if (start == end) {
return 0;
}
return Math.min(
foreHand(start + 1, end);
foreHand(start, end - 1);
);
}
}