Algorithm: Dynamic Programming Understanding(2)
Robot Move Issue
There is an array with length N and a robot,
Robot can move on the array, each time it can only move one step
Calculate: how many ways the robot can move to position P in S steps
Plain Recursion
public class RobotMoveProb {
int targetPosition;
int length;
public calculate(int N, int P, int S) {
length = N;
targetPosition = P;
}
private int process(int curPos, int rest) {
if (rest == 0 || curPos < 0 || curPos > length - 1) {
return curPos == targetPosition ? 1 : 0;
}
if (curPos == 0) {
return process(curPos + 1, rest - 1);
}
if (curPos == length - 1) {
return process(curPost - 1, rest - 1);
}
return process(curPos - 1, rest - 1) + process(curPos + 1, rest - 1);
}
}
Memorized Recursion
in plain recursion version, we can find the parameter list only has two elements:curPos & rest. so it’s a typical memoizable issue
public class RobotMoveProb {
...;
private int processWithCache(int curPos, int rest, int[][] cache) {
if (curPos < 0 || curPos > length - 1 || rest < 0) {
return 0;
}
if (cache[curPos][rest] != 0) {
return cache[curPos][rest];
}
if(curPos == 0) {
return processWithCache(curPos + 1, rest - 1, cache);
}
if (curPos == length - 1) {
return processWithCache(curPos - 1, rest - 1, cache);
}
return processWithCache(curPos - 1, rest - 1, cache) + processWithCache(curPos + 1, rest - 1, cache);
}
}
Dynamic Programming
public class RobotMoveProb {
int targetPosition;
int length;
private int processWithDP(int pos, int rest) {
int[][] dp = new int[length][rest+1];
dp[targetPosition][0] = 1;
for(int col = 1; col <= rest; col++) {
for(int row = 0; row < dp.length; row++) {
if (row == 0) {
dp[row][col] = dp[row+1][col-1];
} else if(row == dp.length - 1) {
dp[row][col] = dp[row - 1][col - 1];
} else {
dp[row][col] = dp[row-1][col-1] + dp[row+1][col - 1];
}
}
}
return dp[pos][rest];
}
}
Pooled Money Problem
given an array representing different money value,
each money can use multiple times,
given a
target, returns how many ways can sum up to this value
Plain Recursion
public class PooledMoney {
private int[] moneys;
public int waysToTarget(int target) {
return process(0, target);
}
private int process(int index, int left) {
if (index == moneys.length) {
return left == 0 ? 1 : 0;
}
if(left == 0) {
return 1;
}
if (left < 0) {
return 0;
}
int ways = 0;
for(int count = 0; count * moneys[index] <= left; count++) {
ways += process(index + 1, left - count * moneys[index]);
}
return ways;
}
}
since the recursion only has two parameters, it’s easy to change to memorized version, let’s just dive into the dynamic programming version
Dynamic Programming
private int processDP() {
int[][] dp = new int[moneys.length][target + 1];
for(int row = 0; row < dp.length; row++) {
dp[row][0] = 1;
}
int left, count;
for(int row = dp.length - 1; row >= 0; row--) {
for(int col = 0; col <= target; col++) {
left = col;
count = 0;
while(left > 0) {
dp[row][col] += dp[row + 1][left - count * money[row]];
left -= count * money[row];
}
}
}
return dp[0][target];
}
Pooled String
A variance of above problem
given an array of string, each element represent a sticker that can be cut.
each sticker can only be used multiple times
given another string
target,calculate at least how many stickers need to be used to get the target
Plain Recursion
public class PoolSticker {
String[] stickers;
public int minStickerToTarget(String target) {
int[][] stickerStats = new int[stickers.length][26];
int[] targetStats = convertStringToInt(target);
return process(stickerStats, targetStats);
}
// at least need how many stickers
private int process(int[][] stickers, int[] target) {
int min = Integer.MAX_VALUE;
if (isEmptyStat(target)) {
return 0;
}
char[] targetChar = convertStatsToCharArr(target);
for(int i = 0; i < stickers.length; i++) {
if(stickers[i][targetChar[0]] == 0) {
continue;
}
int[] copy = target.clone();
min = Math.min(min, process(stickers, removeFromSource(target)));
target = copy;
}
}
private int[] removeFromSource(int[] source, int remove) {
for(int i = 0 ; i < source.length; i++) {
if (source[i] != 0) {
source[i] -= remove[i];
}
}
}
private char[] convertStatsToCharArr(int[] stat) {
StringBuilder sb = new StringBuilder();
for(int i = 0; i < stats.length; i++) {
while(stats[i] != 0) {
sb.append(a + i);
stats[i]--;
}
}
String res = sb.toString();
return res.toCharArray();
}
private boolean isEmptyStat(int[] stats) {
for(int i: stats) {
if (i != 0) {
return false;
}
return true;
}
}
private int[] convertStringToInt(String str) {
char[] cArr = str.toCharArray();
int[] res = new int[26];
for(char c: cArr) {
res[c-'a']++;
}
return res;
}
}
in this solution, the recursive function parameter is not a basic type, which means it cannot be modified to DP version
Longest Common Sub-sequence
given two strings, returns their longest sub-sequence
this is third trial model – line-row model
public class LongestSubSeq {
public String getLongestSubSeq(String a, String b) {
int[][] metrics = new int[a.length][b.length];
char[] aChar = a.toCharArray();
char[] bChar = b.toCharArray();
for (int row = 0; row < metrics.length; row++) {
if (row == 0) {
metrics[0][0] = aChar[0] == bChar[0] ? 1 : 0;
} else {
if (metrics[row-1][0] == 1 || aChar[row] == bChar[0]) {
metrics[row][0] = 1;
} else {
metrics[row][0] = 0;
}
}
}
for(int col = 1; col < metrics[0].length; col++) {
if (metrics[0][col - 1] == 1 || bChar[col] == aChar[0]) {
metrics[0][col] = 1;
}
}
int max;
for(int row = 1; row < metrics.length; row++) {
for(int col = 1; col < metrics[0].length, col++) {
max = Math.max(metrics[row-1][col], metrics[row][col-1]);
if (aChar[row] == bChar[col]) {
max = Math.max(max, metrics[row-1][col-1] + 1);
}
metrics[row][col] = max;
}
}
return metrics[a.length() - 1][b.length() - 1];
}
}