Java dynamic programming example analysis

Explanation

1. Dynamic programming is a programming principle that can be solved by dividing very complex problems into smaller sub-problems.

2. This principle is similar to recursion, but unlike recursion, each different sub-problem can only be solved once.

Use the process

Determine the recursive relationship that is appropriate for the above problem.

Initial memory, array, matrix initial value.

Ensure that when we make a recursive call (with access to the answer to a sub-question), it is always solved ahead of time.

Example

public class dpSolution {  
    static int getValue(int[] values, int rodLength) {
        int[] subSolutions = new int[rodLength + 1];
 
        for (int i = 1; i <= rodLength; i++) {
            int tmpMax = -1;
            for (int j = 0; j < i; j++)
                tmpMax = Math.max(tmpMax, values[j] + subSolutions[i - j - 1]);
            subSolutions[i] = tmpMax;
        }
        return subSolutions[rodLength];
    }
 
    public static void main(String[] args) {
        int[] values = new int[]{3, 7, 1, 3, 9};
        int rodLength = values.length;
 
        System.out.println("Max rod value: " + getValue(values, rodLength));
    }
}

The above is the detailed content of Java dynamic programming example analysis. For more information, please follow other related articles on the PHP Chinese website!