흔히 볼 수 있 는 동적 계획 문제 총화
24835 단어 알고리즘
최 장 증자 시퀀스 (우 객 망 에서 온 것)
하나의 디지털 서열 에 대해 복잡 도 를 O (nlogn) 로 하 는 알고리즘 을 설계 하여 이 서열 의 최 장 상승 서브 서열 의 길 이 를 되 돌려 주 십시오. 여기 의 서브 서열 은 이러한 서열 인 U1, U2 로 정의 합 니 다. 그 중에서 Ui < Ui + 1, 그리고 A [Ui] < A [Ui + 1].디지털 시퀀스 A 와 시퀀스 의 길이 n 을 지정 하고 가장 긴 상승 서브 시퀀스 의 길 이 를 되 돌려 주 십시오.테스트 사례: [2, 1, 4, 3, 1, 5, 6], 7 복귀: 4
여기 서 dp [i] 로 표 지 를 i 로 하 는 요 소 를 증가 서열 의 끝 요소 로 하 는 가장 긴 증가 서브 서열 의 길 이 를 나타 낸다. 여기 서 증가 서열 은 엄격 한 인접 을 요구 하지 않 기 때문에 A [i] 는 모든 A [j] (i > j) 와 비교 해 야 한다. 만약 에 A [i] > A [j] 가 존재 한다 면 i 번 째 요 소 는 j 번 째 요소 뒤에 연결 하여 새로운 증가 서열 의 끝 을 낼 수 있다 는 것 을 의미한다. 따라서 dp [i] = max (dp [j]) + 1;그렇지 않 으 면 i 번 째 요 소 는 앞의 모든 수 보다 작 고 i 요 소 를 마지막 으로 하 는 d 증가 p 시퀀스 의 길 이 는 1 이 므 로 dp [i] = 1 이다.마지막 으로 dp 에서 가장 큰 값 을 꺼 내 면 가장 긴 증가 서브 시퀀스 의 길이 입 니 다.상 태 를 분석 한 후에 문 제 는 쉽게 풀 립 니 다. 여기에 수 동 으로 훑 는 자바 버 전 코드 를 첨부 합 니 다.
public static int[] forward(List list){
int[] dp = new int[list.size()];
dp[0] = 1;
//max j
int max;
for(int i = 1; i < list.size();i++){
max = 0;
for(int j = 0; j < i; j++){
if(list.get(i) > list.get(j)){
max = max < dp[j] + 1 ? dp[j] + 1 : max;
}else{
max = max < 1 ? 1 : max;
}
}
dp[i] = max;
}
return dp;
} 최 장 공공 서브 시퀀스 (우 객 망 에서 온 것)
두 문자열 에 대해 효율 적 인 알고리즘 을 설계 하여 그들의 가장 긴 공공 서열 의 길 이 를 구 하 십시오. 이곳 의 가장 긴 공공 서열 은 두 개의 서열 인 U1, U2, U3... Un 과 V1, V2, V3.. Vn 으로 정의 되 는데 그 중에서 Ui & ltUi + 1, Vi & ltvi + 1 이 있 습 니 다.그리고 A [Ui] = B [Vi].두 문자열 A 와 B 를 지정 하고 두 문자열 의 길이 n 과 m 를 지정 합 니 다. 가장 긴 공공 하위 시퀀스 의 길 이 를 되 돌려 주 십시오.두 줄 의 길이 가 모두 300 보다 작 음 을 보증 합 니 다.테스트 샘플: "1A2C3D4B 56", 10, "B1D23CA45B6A", 12 반환: 6
우 리 는 dp [i] [j] 로 A 문자열 의 앞 i 문자 와 B 문자열 의 앞 j 문자 의 가장 긴 공공 서브 시퀀스 길 이 를 표시 합 니 다. 만약 에 A [i] = B [j] 라면 우 리 는 방정식 dp [i] [j] = dp [i - 1] [j - 1] + 1 을 옮 길 수 있 습 니 다. 만약 에 A [i]! =B[j],dp[i][j] = max(dp[i][j-1],dp[i-1][j])。
public static int findLCS(String A, int n, String B, int m) {
// write code here
int[][] dp = new int[n + 1][m + 1];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(A.charAt(i - 1) == B.charAt(j - 1)){
dp[i][j] = dp[i - 1][j - 1] + 1;
}else{
dp[i][j] = Math.max(dp[i - 1][j - 1],Math.max(dp[i - 1][j],dp[i][j - 1]));
}
}
}
return dp[n][m];
}최 장 공통 꼬치 (우 객 망 에서 온 것)
두 문자열 에 대해 서 는 시간 복잡 도가 O (m * n) 인 알고리즘 (여기 m 와 n 은 두 문자열 의 길이) 을 설계 하여 두 문자열 의 가장 긴 공공 문자열 의 길 이 를 구 하 십시오.여기 서 가장 긴 공공 하위 문자열 은 두 개의 서열 인 U1, U2,.. Un 과 V1, V2,... Vn 으로 정의 되 는데 그 중에서 Ui + 1 = = Ui + 1, Vi + 1 = = Vi + 1, 동시에 Ui = = Vi.두 문자열 A 와 B 를 지정 하고 두 문자열 의 길이 n 과 m 를 동시에 지정 합 니 다.테스트 샘플: "1AB2345CD", 9, "12345 EF", 7 반환: 4
이 문 제 는 위의 문제 와 유사 하 다. 차이 점 은 여기 가 하위 문자열 이 고 연속 적 인 것 이다. dp [i] [j] 는 A 문자열 의 i - 1 문자 와 B 문자열 의 j - 1 문자 로 끝 나 는 가장 긴 공공 문자열 의 길 이 를 나타 낸다. 그러나 A [i - 1] = B [j - 1] 와 dp [i] [j] = dp [i - 1] [j - 1] [j - 1] + 1;A[i-1] != B [j - 1] 때 그들 로 끝 나 는 공공 문자열 의 길 이 는 반드시 0 이다.마지막 으로 dp 에서 길이 가 가장 큰 값 을 꺼 내 면 가장 긴 공공 문자열 입 니 다.
public static int findLongest(String A, int n, String B, int m) {
// write code here
int[][] dp = new int[n + 1][m + 1];
int max = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(A.charAt(i - 1) == B.charAt(j - 1)){
dp[i][j] = dp[i - 1][j - 1] + 1;
}else{
dp[i][j] = 0;
}
if(max < dp[i][j]) max = dp[i][j];
}
}
return max;
}최소 편집 대가 문제 (우 객 망 중점 내용) 는 두 문자열 A 와 B 에 대해 삽입, 삭제, 수정 작업 을 통 해 A 꼬치 를 B 꼬치 로 바 꾸 고 c0, c1, c2 를 각각 세 가지 작업 의 대가 로 정의 해 야 합 니 다. 효율 적 인 알고리즘 을 설계 하여 A 꼬치 를 B 꼬치 로 바 꾸 는 데 필요 한 최소 대 가 를 구 하 십시오.두 문자열 A 와 B, 그리고 그들의 길이 와 세 가지 조작 대 가 를 정 합 니 다. A 문자열 을 B 문자열 로 바 꾸 는 데 필요 한 최소 대 가 를 되 돌려 주 십시오.두 줄 의 길이 가 모두 300 보다 작 고 세 세대 의 가 치 는 모두 100 보다 작 음 을 보증한다.테스트 샘플: "abc", 3, "adc", 3, 5, 3, 100 반환: 8
이 문 제 는 앞의 몇 가지 문제 에 비해 더욱 추상 적 입 니 다. 우 리 는 네 가지 상황 을 정의 해 야 합 니 다. 먼저 dp [i] [j] 는 A 문자열 의 앞 i 문 자 를 B 문자열 의 앞 j 문자 로 바 꾸 는 데 필요 한 대 가 를 표시 합 니 다. 첫 번 째 는 A [i] = B [j] 일 때 우 리 는 어떠한 조작 도 하지 않 아 도 다음 문자 의 비교 에 들 어 갈 수 있 습 니 다. 상태 전이 방정식 은 dp [i] [j] = dp [i - 1] [j - 1] 입 니 다.두 번 째 상황 은 A 문자열 의 마지막 문 자 를 삭제 하여 A 문자열 과 B 문자열 을 같 게 하고 상 태 를 dp [i] [j] = dp [i - 1] [j] + c1 로 이전 하 는 것 입 니 다.세 번 째 는 B 열 에 한 문 자 를 삽입 하여 A 열 과 B 열 을 같 게 하 는 것 이다. 즉, B 열 에서 마지막 문 자 를 제거 하고 A 현재 의 A 열 과 같 으 며 방정식 을 dp [i] [j] = dp [i] [j - 1] + c0 으로 옮 기 는 것 이다.네 번 째 는 A 문자열 의 한 문 자 를 수정 하여 A 문자열 과 B 문자열 을 같 게 하 는 것 이다. 즉, A 문자열 과 B 문자열 의 마지막 문 자 는 같 지 않 고 다른 위 치 는 모두 같 으 며 상태 상 태 는 dp [i] [j] = dp [i - 1] [j - 1] + 1 로 이전 하 는 것 이다.뒤의 세 가지 상황 에서 우 리 는 모두 A 문자열 을 B 문자열 로 바 꿀 수 있 지만, 여기 서 요구 하 는 것 은 최소 의 대가 이기 때문에 dp [i] [j] = min (상황 2, 3, 4).자바 버 전의 코드 는 다음 과 같 습 니 다.
public static int findMinCost(String A, int n, String B, int m, int c0, int c1, int c2) {
// write code here
int[][] dp = new int[n+1][m+1];
for(int i = 0; i <=n; i++) dp[i][0] = i*c0;
for(int j = 0; j <=m; j++) dp[0][j] = j*c1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(A.charAt(i - 1) == B.charAt(j - 1)){
dp[i][j] = dp[i - 1][j - 1];
}else{
dp[i][j] = Math.min(dp[i - 1][j - 1] + c2,Math.min(dp[i][j - 1] + c0,dp[i - 1][j] + c1));
}
}
}
return dp[n][m];
}0 / 1 가방 문제 0 / 1 가방 문 제 는 동적 계획 문제 중의 전형 적 인 문제 설명 입 니 다. 주어진 N 중의 물품 과 가방 입 니 다.아 이 템 i 의 무 게 는 와 이 파이 이 며 그 가 치 는 Vi 이 며 가방 의 용량 은 C 입 니 다.-- 가방 에 들 어 가 는 아 이 템 을 어떻게 선택해 야 가방 에 들 어 가 는 아 이 템 의 총 가 치 를 최대 로 할 수 있 나.아 이 템 을 선택 할 때 각 아 이 템 i 에 대해 서 는 가방 을 넣 거나 가방 을 넣 지 않 는 두 가지 선택 만 있 습 니 다.아 이 템 i 를 여러 번 불 러 올 수도 없고 아 이 템 의 일부분 만 불 러 올 수도 없습니다.이에 따라 이 문 제 는 0 - 1 가방 문제 로 불 린 다.
이 문제 에 대해 우 리 는 최대 가 치 를 Max (N, C) 로 정의 합 니 다. 여기 서 우 리 는 두 가지 상황 으로 나 누 어 상황 을 고려 할 수 있 습 니 다. 하 나 는 가방 에 N 번 째 아 이 템 을 넣 었 습 니 다. 그러면 우 리 는 아직 N - 1 개의 아 이 템 과 C - cn 의 가방 용량 이 남 았 습 니 다. 이런 상황 에서 우리 가 얻 은 가장 큰 가 치 는 Max (N - 1, C - cn) + N * vn 입 니 다.이것 은 바로 위의 문제 의 하위 문제 상황 이다. 2. 가방 에 N 번 째 아 이 템 이 들 어 있 지 않 으 면 우 리 는 N - 1 개의 아 이 템 과 C 의 가방 용량 이 남 았 다. 이런 상황 에서 우리 가 얻 은 가장 큰 가 치 는 Max (N - 1, C) 이다. 위의 분석 을 통 해 우 리 는 dp [i] [j] 가 i 개의 아 이 템 과 j 의 용량 이 있 는 상황 에서 얻 을 수 있 는 가장 큰 가 치 를 정의 할 수 있다.상황 1, 2 를 통 해 상태 이동 방정식 을 쉽게 얻 을 수 있 습 니 다. dp [i] [j] = Max (dp [i - 1] [j - ci] + vi, dp [i - 1] [j]) 를 이해 하기 위해 구체 적 인 0 / 1 가방 인 스 턴 스 를 드 립 니 다.
왕 강 씨 는 오늘 매우 즐 거 웠 습 니 다. 회사 에서 N 위안 의 연말 상 을 주 었 습 니 다.왕 강 은 연말 상 을 쇼핑 에 사용 하기 로 결 정 했 습 니 다. 그 는 사고 싶 은 물건 을 두 가지 로 나 누 었 습 니 다. 메 인 부품 과 첨부 파일, 첨부 파일 은 특정한 메 인 부품 에 속 하 는 것 입 니 다. 첨부 파일 로 분류 되 는 물건 을 사려 면 반드시 이 첨부 파일 에 속 하 는 메 인 부품 을 먼저 사 야 합 니 다.각 주 부품 에는 0 개, 1 개 또는 2 개의 부속품 이 있 을 수 있다.첨부 파일 은 더 이상 자신 만 의 첨부 파일 이 없다.왕 강 은 사고 싶 은 물건 이 많 았 습 니 다. 예산 을 초과 하지 않 기 위해 모든 물건 을 중요 도 를 정 했 습 니 다. 5 등 으로 나 누 었 습 니 다. 정수 1 ~ 5 로 5 등 이 가장 중요 합 니 다.그 는 또 인터넷 에서 모든 물품 의 가격 (모두 10 위안 의 정수 배) 을 찾 아 냈 다.그 는 N 위안 (N 위안 과 같 을 수 있 음) 을 초과 하지 않 는 전제 에서 모든 물품 의 가격 과 중요 도 를 곱 하 는 총계 가 가장 크 기 를 바란다.j 번 아 이 템 의 가격 은 v [j] 이 고 중요 도 는 w [j] 입 니 다. 모두 k 번 아 이 템 을 선 택 했 습 니 다. 번 호 는 j 1, j 2,..., j k 이 고 원 하 는 총 계 는 v [j 1] w [j 1] + v [j 2] * w [j 2] +... + v [j k] * w [j k]] 입 니 다.(그 중 곱 하기) 자바 버 전의 소스 코드 를 직접 드 립 니 다.
import java.util.*;
/**
* Created by on 2017/3/26.
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
String[] moneyAndNum = in.nextLine().split(" ");
int money = Integer.valueOf(moneyAndNum[0]);
int n = Integer.valueOf(moneyAndNum[1]);
int[][] weight = new int[60][3];
int[][] val = new int[60][3];
int[][] dp = new int[n+1][money+1];
int index = 1;
for(int i = 0; i < n; i++){
String[] strs = in.nextLine().split(" ");
int p = Integer.valueOf(strs[0]);
int w = Integer.valueOf(strs[1]);
int q = Integer.valueOf(strs[2]);
if(q == 0){
weight[index][0] = p;
val[index][0] = w * p;
index++;
}else{
if(weight[index - 1][1] == 0){
weight[index - 1][1] = p;
val[index - 1][1] = w * p;
}else{
weight[index - 1][2] = p;
val[index - 1][2] = w * p;
}
}
}
for(int i = 1; i < n + 1; i++){
for(int j = 1; j < money + 1; j++){
//j i
if(weight[i][0] <= j){
//dp[i - 1][j] i ，dp[i - 1][j - weight[i][0]] i
dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - weight[i][0]] + val[i][0]);
}
if(weight[i][0] + weight[i][1] <= j){
dp[i][j] = Math.max(dp[i][j],Math.max(dp[i - 1][j],dp[i - 1][j - weight[i][0] - weight[i][1]] + val[i][0] + val[i][1]));
}
if(weight[i][0] + weight[i][2] <= j){
dp[i][j] = Math.max(dp[i][j],Math.max(dp[i - 1][j],dp[i - 1][j - weight[i][0] - weight[i][2]] + val[i][0] + val[i][2]));
}
if(weight[i][0] + weight[i][1] + weight[i][2] <= j){
dp[i][j] = Math.max(dp[i][j],Math.max(dp[i - 1][j],dp[i - 1][j - weight[i][0] - weight[i][1] - weight[i][2]] + val[i][0] + val[i][1] + val[i][2]));
}
}
}
System.out.println(dp[n][money]);
}
}
}
주식 수익 최대 화 문제 (leetcode 에서 온) 주식 수익 최대 화 문제 1
주식 수익 의 최대 화 문제 2 는 한 배열 이 있다. 배열 중의 i 번 째 수 는 i 일 주식 의 가격 을 나타 낸다. 지금 은 알고리즘 을 설계 하여 최대 화 된 주식 수익 을 얻 도록 요구한다. 여 기 는 가능 한 한 여러 번 의 거래 를 할 수 있 지만 거래 는 교차 할 수 없다. 즉, 주식 을 사기 전에 반드시 이전 주식 을 팔 아야 한다.여기 서 상태 이전 문 제 를 분석 하 겠 습 니 다. i 일 째 에 우 리 는 주식 의 가격 을 관찰 합 니 다. 만약 에 price [i] > price [i - 1] 는 i 일 째 i - 1 일 에 상대 적 으로 수익 이 있다 는 것 을 나타 냅 니 다. 만약 에 우리 가 i 일 째 에 주식 을 팔 면 i - 1 일 에 비해 수익 이 증가 하고 방정식 은 dp [i - 1] + price [i] - 1] - price [i - 1], price [i] < = price [i - 1] 입 니 다. 만약 에 우리 가 i 일 째 에 주식 을 팔 면...손실 이기 때문에 우 리 는 주식 을 계속 보유 하고 있 습 니 다. 즉, 방정식 은 dp [i] = dp [i - 1] 입 니 다.어떤 친구 들 은 곤 혹 스 러 울 수도 있 습 니 다. 여 기 는 매도 조작 만 있 습 니 다. 그러면 언제 주식 을 사 들 였 는 지 어떻게 알 겠 습 니까? 우 리 는 자세히 분석 해 보면 주식 이 하락 할 때 어떠한 조작 도 하지 않 고 수익 도 없 으 며 주식 가격 이 가장 낮 고 상승 하기 시 작 했 을 때 우 리 는 사 들 이기 시 작 했 습 니 다.그리고 주가 가 가장 높 을 때 던 져 요.참고 자바 버 전 코드 를 드 리 겠 습 니 다:
public class Solution {
public int maxProfit(int[] prices){
int[] dp = new int[prices.length];
if(prices.length == 0) return 0;
dp[0] = 0;
for(int i = 1; i < prices.length;i++){
if(prices[i] > prices[i - 1]){
dp[i] = dp[i - 1] + prices[i] - prices[i - 1];
}else{
dp[i] = dp[i - 1];
}
}
return dp[prices.length - 1];
}
}
** **기 존의 분동 은 무게 가 서로 같 지 않 고 각각 m1, m2, m3... mn 이다.각 분동 에 대응 하 는 수량 은 x1, x2, x3... xn 이다.지금 은 이 분동 으로 물체 의 무 게 를 달 아서 얼마나 다른 무 게 를 달 수 있 는 지 물 어 봐 야 한다.
주: 무게 측정 은 0 입력 설명 을 포함 합 니 다. 입력 은 여러 그룹의 테스트 데 이 터 를 포함 합 니 다.
각 그룹의 테스트 데이터:
첫 번 째 줄: n - 분동 수 (범위 [1, 10])
두 번 째 줄: m1 m2 m3... mn - 각 분동 의 무게 (범위 [1, 2000])
세 번 째 줄: x1 x2 x3... xn - 각 분동 의 수량 (범위 [1, 6])
이곳 의 상태 전이 방정식 은 쉽게 얻 을 수 있 으 며, 사용 가능 한 분동 수량 이 0 이 아 닌 상황 에서 w - mi 의 무 게 를 달 수 있다 면 w 의 무게 도 달 수 있다.이 상태 전이 방정식 을 바탕 으로 우 리 는 크기 가 총 무게 인 배열 을 정의 할 수 있 습 니 다. 모든 무 게 를 표시 할 수 있 는 지, 즉 max Weight = mi * xi (0) 를 표시 할 수 있 습 니 다.
import java.util.Scanner;
/**
* Created by on 2017/4/23.
*/
public class Main {
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int n = in.nextInt();
int[] m = new int[n];
int[] x = new int[n];
for(int i = 0; i < n;i++){
m[i] = in.nextInt();
}
for(int i = 0; i < n; i++){
x[i] = in.nextInt();
}
int max = 0;
for(int i = 0; i < n;i++){
max += m[i] * x[i];
}
int[] dp = new int[max + 1];
dp[0] = 1;
for(int i = 0; i < n;i++){
for(int k = max; k >= 1;k--){
for(int j = x[i]; j >= 0;j--){
if((k-j * m[i] >= 0) && (dp[k-j * m[i]] == 1)){
dp[k] = 1;
}
}
}
}
int num = 0;
for(int i = 0; i <= max; i++){
if(dp[i] == 1){
num++;
}
}
System.out.println(num);
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
