DSA/DynamicProgramming.java at main · deepsol718/DSA · GitHub

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
public class DynamicProgramming {
    DynamicProgramming(){
//    sumEqualToK();\
//        int[][] arr = {{5,7,2,4},{1,8,1,3},{6,2,9,5},{1,6,2,8}};
//        for (int[] x: arr){
//            for (int y : x){
//                System.out.print(y+" ");
//            }
//            System.out.println();
//        }
//        System.out.println(minCostPath(arr));
//        new Pattern();
        lcs();//longest common substring
    }

    private void lcs() {
        String s1 = "sdfsf";
        String s2 = "dfgvbrghcf";
        int ans = lcsHelper(s1,s2);
    }

    private int lcsHelper(String s1, String s2) {
        if (s1.length() == 0 || s2.length() == 0) return 0;

        if (s1.charAt(0) == s2.charAt(0)){
            return 1 + lcsHelper(s1.substring(1) , s2.substring(1));
        }
        else{
            int one = lcsHelper(s1, s2.substring(1));
            int two = lcsHelper(s1.substring(1), s2);
            return Math.max(one,two);
        }
    }


    public void sumEqualToK(){
        int[] coins = {1,2,3,4,5,6};

        int sum = 6;
        printCoinsUpToK(coins, sum, "");

    }

    public void printCoinsUpToK(int[] coins, int k, String s){
        if (k == 0){
            System.out.println(s);
            return;
        }
        if (k < 0) return;

        for (int i = 0; i < coins.length; i++){
            printCoinsUpToK(coins,k-coins[i], s +" "+coins[i]);
        }
    }

    public static int minCostPath(int[][] input) {
        int m = input.length;
        int n = input[0].length;
        int[][] dp = new int[m][n];

        int index = 1;

        int min = Math.min(m,n);

        while(index <= min){
            int i = m - index;
            int j = n - index;
            for ( ; i >=0; i-- ){
                int a = Integer.MAX_VALUE;
                int b = Integer.MAX_VALUE;
                int c = Integer.MAX_VALUE;

                if (i + 1 < m) a = dp[i+1][j];
                if (j + 1 < n) b = dp[i][j+1];
                if (i + 1 < m && j + 1 < n) c = dp[i+1][j+1];

                int minimum = Math.min(a,Math.min(b,c));

                if (minimum == Integer.MAX_VALUE){
                    dp[i][j] = input[i][j];
                    continue;
                }

                dp[i][j] = input[i][j] + minimum;

            }

            i = m - index;
            for ( ; j >=0; j-- ){
                int a = Integer.MAX_VALUE;
                int b = Integer.MAX_VALUE;
                int c = Integer.MAX_VALUE;

                if (i + 1 < m) a = dp[i+1][j];
                if (j + 1 < n) b = dp[i][j+1];
                if (i + 1 < m && j + 1 < n) c = dp[i+1][j+1];

                int minimum = Math.min(a,Math.min(b,c));

                if (minimum == Integer.MAX_VALUE){
                    dp[i][j] = input[i][j];
                    continue;
                }

                dp[i][j] = input[i][j] + minimum;

            }

            index++;
        }
//        for (int[] x: dp){
//            for (int y : x){
//                System.out.print(y+" ");
//            }
//            System.out.println();
//        }
        return dp[0][0];
    }
}