基于dynamix编程的利润最大化

Question

我一直在尝试解决这个问题：“你必须到不同的村庄去赚钱。在每个村庄，你都会获得一些利润。但问题是，从一个特定的村庄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];
    }

Answer 1

我使用了额外的数组来得到解决方案，我的代码是用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] && p[i]%p[j]==0 && 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;
    }