# Dynamic Programming & Memorization

## 由来

LC377 Combination Sum IV

``````public class Solution {
// combinations[target]
// = sum(combinations[target-nums[i]]), i : 0 -> n
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target+1];
dp[0] = 1;
for(int i = 1; i < dp.length; i++) {
for(int j = 0; j < nums.length; j++) {
if(i - nums[j] >= 0) {
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
}
}
``````

``````public class Solution {
private int[] dp;
public int combinationSum4(int[] nums, int target) {
dp = new int[target + 1];
Arrays.fill(dp, -1);
dp[0] = 1;
return helper(nums, target);
}

private int helper(int[] nums, int target) {
if (dp[target] != -1) {
return dp[target];
}
int res = 0;
for (int i = 0; i < nums.length; i++) {
if (target >= nums[i]) {
res += helper(nums, target - nums[i]);
}
}
dp[target] = res;
return res;
}
}
``````

## 结论

What is difference between memoization and dynamic programming?

Memoization is a term describing an optimization technique where you cache previously computed results, and return the cached result when the same computation is needed again.

Dynamic programming is a technique for solving problems recursively and is applicable when the computations of the subproblems overlap.

Dynamic programming is typically implemented using tabulation, but can also be implemented using memoization. So as you can see, neither one is a “subset” of the other.

A reasonable follow-up question is: What is the difference between tabulation (the typical dynamic programming technique) and memoization?

When you solve a dynamic programming problem using tabulation you solve the problem “bottom up”, i.e., by solving all related sub-problems first, typically by filling up an n-dimensional table. Based on the results in the table, the solution to the “top” / original problem is then computed.

If you use memoization to solve the problem you do it by maintaining a map of already solved sub problems. You do it “top down” in the sense that you solve the “top” problem first (which typically recurses down to solve the sub-problems).

A good slide from here (link is now dead, slide is still good though):

• If all subproblems must be solved at least once, a bottom-up dynamic-programming algorithm usually outperforms a top-down memoized algorithm by a constant factor