-
Notifications
You must be signed in to change notification settings - Fork 0
/
DP_Part_5.java
147 lines (114 loc) · 4.17 KB
/
DP_Part_5.java
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
package Dynamic_Programming;
import java.util.Arrays;
public class DP_Part_5 {
// MATRIX CHAIN MULTIPLICATION
public static int MCM_Recursion(int[] arr, int i, int j){
// single matrix in a set : base case
if (i==j) return 0;
int ans = Integer.MAX_VALUE;
for (int k=i; k<j; k++){
int cost1 = MCM_Recursion(arr, i, k); // arr[i-1] * arr[k]
int cost2 = MCM_Recursion(arr, k+1, j); // arr[k] * arr[j]
int cost3 = arr[i-1] * arr[k] * arr[j];
ans = Math.min(ans, cost1+cost2+cost3);
}
return ans;
}
// Using Memoization -> O(n^3)
public static int MCM_memo(int[] arr, int i, int j, int[][] dp){
int ans = Integer.MAX_VALUE;
if (i==j) return 0; // single matrix
for (int k=i; k<j; k++){
int cost1 = MCM_memo(arr, i, k, dp); // arr[i-1] * arr[i] x arr[k-1] * arr[k] = arr[i-1] * arr[k]
int cost2 = MCM_memo(arr, k+1, j, dp); // arr[k+1-1] * arr[k+1] x arr[j-1] * arr[j] = arr[k+1-1] * arr[j]
int cost3 = arr[i-1] * arr[k] * arr[j];
ans = Math.min(ans, cost1+cost2+cost3);
}
return dp[i][j] = ans;
}
// Minimum array partitioning
public static int minSumPart(int[] arr){
int n = arr.length;
// calculate sum of arr
int sum = 0;
for (int i=0; i<arr.length; i++){
sum += arr[i];
}
int W = sum/2;
int[][] dp = new int[n+1][W+1];
for (int i=0; i<dp.length; i++){
Arrays.fill(dp[i], -1);
}
int sum1 = knapSackTab(arr, W);
int sum2 = sum - sum1;
return Math.abs(sum1 - sum2);
}
public static int knapSackTab(int[] arr, int W){
int n = arr.length;
int[][] dp = new int[n+1][W+1];
for (int i=1; i< dp.length; i++){
for (int j=1; j<dp[0].length; j++){
// valid
if (arr[i-1] <= j){
int take = arr[i-1] + dp[i-1][j-arr[i-1]];
int notTake = dp[i-1][j];
dp[i][j] = Math.max(take, notTake);
}else{
dp[i][j] = dp[i-1][j];
}
}
}
return dp[n][W];
}
public static int knapSack(int[] arr, int W, int[][] dp, int n){
if (n==0 || W==0) return 0;
// valid
if (arr[n-1] <= W){
int take = arr[n-1] + knapSack(arr, W-arr[n-1], dp, n-1);
int notTake = knapSack(arr, W, dp, n-1);
return dp[n][W] = Math.max(take, notTake);
}else{
return dp[n][W] = knapSack(arr, W, dp ,n-1);
}
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 3};
int n = arr.length;
System.out.println(MCM_Recursion(arr, 1, n-1));
int[][] dp = new int[n][n];
for (int ind=0; ind<dp.length; ind++){
Arrays.fill(dp[ind], -1);
}
System.out.println(MCM_memo(arr, 1, n-1, dp));
int[] arr2 = {1, 6, 11, 5};
System.out.println(minSumPart(arr2));
}
public static int frogJump(int n , int[] arr, int[] dp){
if (n==0) return 0;
if (dp[n] != -1) return dp[n];
int oneJump = frogJump(n-1, arr, dp) + Math.abs(arr[n]-arr[n-1]);
int twoJump = Integer.MAX_VALUE;
if (n>1) {
twoJump = frogJump(n-2, arr, dp) + Math.abs(arr[n]-arr[n-2]);
}
dp[n] = Math.min(oneJump, twoJump);
return dp[n];
}
public static int frogJump(int[] arr, int n, int k){
int[] dp = new int[n+1];
dp[0] = 0;
int minStep = 0;
int jumps = 0;
for (int i=1; i<n; i++){
minStep = Integer.MAX_VALUE;
for (int j=1; j<=k; j++){
if (i-j >= 0) {
jumps = dp[i - j] + Math.abs(arr[i - j] - arr[i]);
minStep = Math.min(jumps, minStep);
}
}
dp[i] = minStep;
}
return dp[n-1];
}
}