Practice/Dynamic.cpp at master · jeetabhi01/Practice · 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
#include<iostream>
#include<algorithm>

using std::cin;
using std::cout;
using std::endl;

class Dynamic{
    private:
        int minimumHelper(int n ,int * arr);
    public:
       int minimumR(int n){
        if(n==1){
           return 0;
        }
        int x = minimumR(n-1);
        int y = __INT_MAX__;
        int z = __INT_MAX__;
        if(n%2==0){
            y =minimumR(n/2);
        }
        if(n%3==0){
           z = minimumR(n/3);
        }

        int ans = std::min(x,std::min(y,z)) + 1;
        return ans;
    }

    int minimum(int n);

};

signed main(){
    Dynamic a;
    int n = 10;

    cout<<a.minimumR(10)<<endl;
    cout<<a.minimum(10)<<endl;

    return 0;
}


int Dynamic::minimumHelper(int n , int *ans){
    if(n == 1){
        ans[n] = 0;
        return 0;
    }
    else{
    int y = __INT_MAX__;
    int z = __INT_MAX__;
    if(ans[n-1] == -1){
        ans[n-1] = minimumHelper(n-1,ans);
    }
    int x = ans[n-1];
    if(n%2==0){
        if(ans[n/2] == -1){
            ans[n/2] = minimumHelper(n/2,ans);
        }
        y = ans[n/2];
    }

    if(n%3 == 0){
        if(ans[n/3]==-1){
            ans[n/3] = minimumHelper(n/3,ans);
        }
        z = ans[n/3];
    }
    cout<<x<<" "<<y<<" "<<z<<endl;
    ans[n] = std::min(x,std::min(y,z))+1;
    return ans[n];
    }
}
int Dynamic::minimum(int n){
    int * ans = new int[n+1]{-1};
    int output = Dynamic::minimumHelper(n,ans);
    delete []ans;
    return output;
}