Dynamic Programming

2022-03-06 674 words 4 minutes

Contents

Theory

Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman🧐 in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.

In both contexts it refers to simplifying a complicated problem by breaking it down into simpler sub-problems. If a problem can be solved optimally by breaking it into sub-problems and finding the optimal solutions to the sub-problems, then it is said to have optimal substructure.

The means that dynamic programming problems have an ordering of simpler to more complex problems and those have problems have a optimal substructure.

These problems often involve recursion. If sub-problems can be nested recursively inside larger problems, so that dynamic programming methods are applicable, then there is a relation between the value of the larger problem and the values of the sub-problems.

Tips to remember

Recursion is a way to solve problems from bigger to smaller, and it will not record any subsolutions. Only considers:
- Base Case (the smallest problem we have to solve)
- Recursive Rule
Dynamic Programming solves problems from smaller to bigger, and it will record subsolutions. It considers:
- Mathematical Expression (??)
- Base Case
- Induction rule (??)
- Subsolution which its size < n $\rightarrow$ Solution which its size = n

Why Dynamic programming can solve problems like how to get an optimal solution (try to figure out the MIN or MAX result), because it will consider every situation.

Programming Problems

0-1 Knapsack Problem

description

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item or don’t pick it (0-1 property).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26



	public static int solution(int[] val, int[] weight, int lmt) {
		int[][] ans = new int[val.length + 1][lmt + 1];

		for (int i = 0; i <= val.length; i++) {
			for (int j = 0; j <= lmt; j++) {
				if (i == 0 || j == 0) {
					ans[i][j] = 0;
				} else if (weight[i - 1] <= j) {
					ans[i][j] = Math.max(val[i - 1] + ans[i - 1][j - weight[i - 1]], ans[i - 1][j]);
				} else {
					ans[i][j] = ans[i - 1][j];
				}
			}
		}

		return ans[val.length][lmt];
	}

	public static void main(String[] args) {
		int[] val = new int[] { 60, 100, 120 };
        int[] weight = new int[] { 10, 20, 30 };
        int limit = 50;
        System.out.println(Test.solution(val, weight, limit));
	}

Change Making Problem

description

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example:

1
2
3


Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


	public class Solution {
	    public int coinChange(int[] coins, int amount) {
	        int max = amount + 1;
	        int[] dp = new int[amount + 1];
	        Arrays.fill(dp, max);
	        dp[0] = 0;
	        for (int i = 1; i <= amount; i++) {
	            for (int j = 0; j < coins.length; j++) {
	                if (coins[j] <= i) {
	                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
	                }
	            }
	        }
	        return dp[amount] > amount ? -1 : dp[amount];
	    }
	}