2 Keys Keyboard Dynamic solution


  • 0
    S

    d[n-1] represents minimum number of steps to print n 'A's on screen.
    d[i-1]=minimum(d[k-1]+n/k) , if n%k=0 and for k in [1,(n/2)]
    Initialising d[0]=0

    public int minSteps(int n) {
            int d[]=new int[n];
            d[0]=0;
            for(int i=2;i<=n;i++){
                int m=Integer.MAX_VALUE;
                for(int j=1;j<=(i/2);j++){
                 if(i%j==0){
                     if((d[j-1]+(i/j))<m){
                            m=d[j-1]+(i/j);
                     }
                 }
                }
                d[i-1]=m;
            }
            return d[n-1];
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.