Untitled
unknown
plain_text
13 days ago
775 B
2
Indexable
Never
int solution(int n, int[] prices) { int[] dp = new int[n + 1]; // Initialize dp array to store the maximum revenue for each length for (int i = 0; i <= n; i++) { dp[i] = 0; } // Iterate for each length of rod from 1 to n for (int i = 1; i <= n; i++) { int maxVal = Integer.MIN_VALUE; // Try every possible cut of the rod of length i for (int j = 1; j <= i; j++) { maxVal = Math.max(maxVal, prices[j] + dp[i - j]); } // Store the maximum revenue for length i dp[i] = maxVal; } // The maximum revenue for length n is stored in dp[n] return dp[n]; }
Leave a Comment