Блог

Я пытался решить эту проблему: » Вы должны путешествовать по разным деревням, чтобы получить какую-то прибыль. В каждой деревне вы получаете некоторую прибыль. Но загвоздка в том, что из конкретной деревни i вы можете перейти в деревню j только тогда и только тогда, когда прибыль от деревни j кратна прибыли от деревни i.

Вы должны указать максимальную прибыль, которую вы можете получить во время путешествия. «

Вот ссылка на полную проблему: https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/practice-problems/algorithm/avatar-and-his-quest-d939b13f/description/

Я пытался решить эту проблему в течение нескольких часов. Я знаю, что это вариант самой длинной возрастающей подпоследовательности, но первая мысль, которая пришла мне в голову, заключалась в том, чтобы решить ее с помощью рекурсии, а затем запомнить ее. Вот часть кода моего подхода. Пожалуйста, помогите мне определить ошибку.

     static int[] dp;
    static int index;
    static int solve(int[] p) {
        int n = p.length;
        int max = 0;
        for(int i = 0;i<n; i  )
        {
            dp = new int[i 1];
            Arrays.fill(dp,-1);
            index = i;
            max = Math.max(max,profit(p,i));
        }
        return max;
    }
    static int profit(int[] p, int n)
    {
        if(dp[n] == -1)
        {
            if(n == 0)
            {
                if(p[index] % p[n] == 0)
                    dp[n] = p[n];
                else
                    dp[n] = 0;
            }
            else
            {
                int v1 = profit(p,n-1);
                int v2 = 0;
                if(p[index] % p[n] == 0)
                    v2 = p[n]   profit(p,n-1);
                dp[n] = Math.max(v1,v2);
            }
        }
        return dp[n];
    }
  

Я использовал дополнительный массив для получения решения, мой код написан на Java.

 public static int getmaxprofit(int[] p, int n){
       // p is the array that contains all the village profits 
       // n is the number of villages
       // used one extra array msis, that would be just a copy of p initially
       int i,j,max=0;
       int msis[] = new int[n];

       for(i=0;i<n;i  ){
           msis[i]=p[i];
       }
       // while iteraring through p, I will check in backward and find all the villages that can be added based on criteria such previous element must be smaller and current element is multiple of previous.

       for(i=1;i<n;i  ){
           for(j=0;j<i;j  ){
               if(p[i]>p[j] amp;amp; p[i]%p[j]==0 amp;amp; msis[i] < msis[j] p[i]){
                   msis[i] = msis[j] p[i];
               }
           }
       }
       for(i=0;i<n;i  ){
           if(max < msis[i]){
               max = msis[i];
           }
       }
       return max;
    }