동적 계획 면접 문제 (최대 필드 와 / 삼각 배열 최대 와 / LIS 최 장 비 하강 서브 시퀀스 / LCS 최 장 (연속 / 비 연속) 공공 서브 시퀀스)
11058 단어 알고리즘
설명: n 개의 정수 (음수 일 수 있 음) 로 구 성 된 서열 a [1], a [2], a [3]. 주어진 정수 가 모두 마이너스 일 때 하위 세그먼트 와 0 을 정의 합 니 다. 만약 에 시퀀스 에 모두 마이너스 라면 최대 하위 단 과 0 입 니 다. 이 정의 에 따라 원 하 는 최 적 화 된 값 은 Max {0, a [i] + a [i + 1] 입 니 다. +....+a [1}, 1 ≤ i ≤ j ≤ n. 입력: - 2, 11, - 4, 13, - 5, - 2 ；출력: 20
분석: 상태 dp [i] 는 i 번 째 요소 로 끝 나 는 최대 필드 와
dp[0] : 0
dp[1] : 11 + dp[0] = 11
dp[2] : -4 + dp[1] = 7
dp[3] : 13 + dp[2] = 20
dp[4] : -5 + dp[3] = 15
dp[5] : -2 + dp[4] = 13
dp[0] = 0
：dp[i] = ar[i] + dp[i-1]코드:
import java.util.Arrays;
public class sum {
public static void main(String[] args) {
int[] arr = new int[]{-2,11,-4,13,-5,-2};
int[] dp = new int[arr.length];
int sum = maxSegmentSum(arr,dp);
System.out.println (Arrays.toString (dp));
System.out.println (sum);
}
private static int maxSegmentSum(int[] arr, int[] dp) {
dp[0] = arr[0];
// 0
if (dp[0] < 0){
dp[0] = 0;
}
int max = dp[0];
for (int i = 1; i < arr.length; i++) {
dp[i] = arr[i] + dp[i-1];
if(dp[i] < 0){
dp[i] = 0;
}
// max
if(max < dp[i]){
max = dp[i];
}
}
return max;
}
}
2. 삼각 배열 의 최대 값
설명:
/**
* :
* ， ：
* 5
* 12 6
* 7 13 18
* 12 14 10 9
* ， ， ，
* ， ， ？
*
*/사고: 우 리 는 먼저 마지막 층 의 요 소 를 옮 겨 다 니 며 dp 에 저장 한 다음 에 마지막 두 번 째 열 에서 아래로 선택 할 수 있 습 니 다. 즉, 모든 수 는 세 가지 추가 가능 (마지막 층 요 소 를 선택) 이 있 습 니 다. 추 가 된 수 에서 최대 수 를 dp 에 저장 한 다음 에 한 층 씩 위로 옮 겨 다 니 면 모든 층 의 요소 가 최대 와 최대 화 를 구 할 수 있 습 니 다.
void func(int[] arr, int i, int j){ arr [i] [j] + func (arr [i + 1] [j]); / 아래 에 추가 arr [i] [j] + func (arr [+ 1] [j - 1]); / / 왼쪽으로 비스듬히 arr [i] [j] + func (arr [+ 1] [j + 1]); / / 오른쪽으로 비스듬히
}
코드:
public class {
public static void main(String[] args) {
int[][] arr = new int[][]{
{5},
{12, 6},
{7, 13, 18},
{12, 14, 10, 9}
};
int[][] dp = new int[arr.length][arr.length];
int row = arr.length - 1;
// dp,
for (int i = 0; i < arr[row].length; i++) {
dp[row][i] = arr[row][i];
}
int sum = maxSum (arr,dp);
System.out.println (sum);
// // ：
// int max = func (arr,0,0,dp);
// System.out.println (max);
}
/**
*
*/
private static int maxSum(int[][] arr, int[][] dp) {
// （ dp）
for (int i = arr.length - 1 - 1; i >= 0; i--) {
for (int j = 0; j < arr[i].length; j++) {//
//
int n1 = arr[i][j] + dp[i+1][j];
//
int n2 = arr[i][j] + dp[i+1][j+1];
int n3 = 0;
// ，
if(j > 0){
n3 = arr[i][j] + dp[i+1][j-1];
}
// dp
dp[i][j] = Math.max (Math.max(n1,n2),n3);
}
}
return dp[0][0];
}
/**
*
* @param arr
* @param i
* @param j
* @param dp
* @return
*/
private static int func(int[][] arr, int i, int j, int[][] dp) {
//
if(i > arr.length-1 || j < 0 || j > arr[i].length-1){
return 0;
}
//
if(dp[i][j] > 0){
return dp[i][j];
}
int n1 = arr[i][j] + func(arr, i+1, j, dp);
int n2 = arr[i][j] + func(arr, i+1, j-1, dp);
int n3 = arr[i][j] + func(arr, i+1, j+1, dp);
dp[i][j] = Math.max(Math.max(n1, n2), n3);
return dp[i][j];
}
}
3. LIS 최 장 비강 자 서열 문제 구하 기
설명: 문자열 을 지정 합 니 다. 그 중에서 가장 긴 문자열 의 길 이 를 작은 것 에서 큰 것 으로 정렬 합 니 다.
/**
* dp[i] i ，
* ：dp(i) = max{1, dp(j)+1}
* j dp[i]){
dp[i] = dp[j] + 1;
}
}
if(max < dp[i]){
max = dp[i];
}
}
return max;
}
}4. LCS 최 장 (연속 / 반드시 연속 되 지 않 음) 공공 하위 서열 문제 구하 기
두 서열 의 최 장 공공 서열 (연속) 의 길 이 를 구하 십시오.
/**
*
* ：dp[m][n]
* :
* dp[m][n]=1 + dp[m-1][n-1] (str1[i]=str2[j])
*/
public class test {
public static void main(String[] args) {
String str1 = "helloworld";
String str2 = "helxtld";
int[][] dp = new int[str1.length () + 1][str2.length () + 1];
int sum = func (str1, str2, dp);
System.out.println (sum);
}
private static int func(String str1, String str2, int[][] dp) {
int k = 0;
int max = 0;
for (int m = 1; m <= str1.length (); ++m) {
for (int n = 1; n <= str2.length (); ++n) {
if (str1.charAt (m - 1) == str2.charAt (n - 1)) {
dp[m][n] = 1 + dp[m - 1][n - 1]; //
}
if (max < dp[m][n]) {
max = dp[m][n];
// ， k
k = m;
}
}
}
//substring()
System.out.println (str1.substring ((k-max),k));
return max;
}
}
실행 결과:
우 리 는 공공 문자열 의 길이 와 공공 문자열 을 얻 을 수 있 습 니 다.
hel
3두 서열 의 최 장 공공 하위 서열 (연속 되 지 않 음) 의 길 이 를 구하 십시오.
public class test {
public static void main(String[] args) {
String str1 = "helloworld";
String str2 = "helxtld";
int[][] dp = new int[str1.length ()+1][str2.length ()+1];
// int lcs = func (str1, str2,str1.length ()-1,str2.length ()-1, dp);
int lcs1 = func (str1,str2,dp);
// System.out.println (lcs);
System.out.println (lcs1);
// for (int i = 0; i < dp.length; i++) {
// for (int j = 0; j < dp[i].length; j++) {
// System.out.print (dp[i][j] + " ");
// }
// System.out.println ();
// }
}
}
/**
* LCS
* @param str1
* @param str2
* @param dp
* @return
*/
private static int func(String str1, String str2, int[][] dp) {
/**
* dp[m][n] : str1 m ，str2 n
* LCS
*
* if(xm == yn)
* dp[m][n] = 1 + dp[m-1][n-1]
* else {
* dp[m][n] = max{dp[m][n-1], dp[m-1][n]}
* }
*/
for(int m=1; m<=str1.length(); m++){
for(int n=1; n<=str2.length(); n++){
if(str1.charAt(m-1) == str2.charAt(n-1)){
dp[m][n] = 1 + dp[m-1][n-1]; //
} else {
if(dp[m][n-1] > dp[m-1][n]){
dp[m][n] = dp[m][n-1]; //
} else {
dp[m][n] = dp[m-1][n]; //
}
}
}
}
return dp[str1.length()][str2.length()];
}
/**
*
* @param str1
* @param str2
* @param m
* @param n
* @param dp
* @return
*/
private static int func(String str1, String str2, int m, int n, int[][] dp) {
if(m < 0 || n < 0){
return 0;
}
if(dp[m][n] > 0){
return dp[m][n];
}
if(str1.charAt(m) == str2.charAt(n)){
dp[m][n] = 1 + func(str1, str2, m-1, n-1, dp);
return dp[m][n];
} else {
int n1 = func(str1, str2, m, n-1, dp);
int n2 = func(str1, str2, m-1, n, dp);
if(n1 > n2){
dp[m][n] = n1;
} else {
dp[m][n] = n2;
}
return dp[m][n];
}
}
}위의 코드 는 가장 긴 공공 서브 시퀀스 의 길 이 를 인쇄 할 뿐 입 니 다. 가장 긴 공공 서브 시퀀스 의 요 소 를 인쇄 하려 면 dp 표 의 방향 을 기록 한 다음 에 역 추적 법 으로 요 소 를 인쇄 해 야 합 니 다. 코드 는 다음 과 같 습 니 다.
public static void main(String[] args) {
String str1 = "helloworld";
String str2 = "helxtld";
int[][] dp = new int[str1.length () + 1][str2.length () + 1];
// ， LCS
int[][] path = new int[str1.length () + 1][str2.length () + 1];
int lcs = func (str1, str2, dp, path);
System.out.println (" ：" + lcs);
// bp ， bp
for (int i = 0; i < dp.length; i++) {
for (int j = 0; j < dp[i].length; j++) {
System.out.print (dp[i][j] + " ");
}
System.out.println ();
}
backstrace (str1, str1.length (), str2.length (), path);
}
// ， ，
private static void backstrace(String str1, int m, int n, int[][] path) {
if (m < 0 || n < 0) {
return;
}
if (path[m][n] == 1) {
backstrace (str1, m - 1, n - 1, path);
System.out.print (str1.charAt (m - 1));
} else {
if (path[m][n] == 2) {
backstrace (str1, m, n - 1, path);
} else {
backstrace (str1, m - 1, n, path);
}
}
}
private static int func(String str1, String str2, int[][] dp, int[][] path) {
for (int m = 1; m <= str1.length (); ++m) {
for (int n = 1; n <= str2.length (); ++n) {
if (str1.charAt (m - 1) == str2.charAt (n - 1)) {
dp[m][n] = 1 + dp[m - 1][n - 1]; //
path[m][n] = 1;
} else {
if (dp[m][n - 1] > dp[m - 1][n]) {
dp[m][n] = dp[m][n - 1]; //
path[m][n] = 2;
} else {
dp[m][n] = dp[m - 1][n]; //
path[m][n] = 3;
}
}
}
}
return dp[str1.length ()][str2.length ()];
}
}실행 결과:
：5
0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1
0 1 2 2 2 2 2 2
0 1 2 3 3 3 3 3
0 1 2 3 3 3 4 4
0 1 2 3 3 3 4 4
0 1 2 3 3 3 4 4
0 1 2 3 3 3 4 4
0 1 2 3 3 3 4 4
0 1 2 3 3 3 4 4
0 1 2 3 3 3 4 5
helld인쇄 된 bp 표 는 대각선 에서 증가 하 는 수, 즉 공공 하위 시퀀스 의 길 이 를 기록 합 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
