편집기는 크기가 다른 경우와 더 나은 읽기 체험 스탬프 가능한 WizNote: 동적 기획
가방
dp[i][j]: i번째 아이템부터 총 무게가 j보다 적을 때 총 가치의 최대치 O(nW) 선택
(i역순, j순)
i:n-1~0 j:0~W
1. 남은 물건이 없습니다(i<0)
2. 이 아이템을 고를 수 없다(j)
3. 선택 여부를 선택할 수 있다면(dp[i][j]=max(dp[i+1][j], dp[i+1][j-w[i]]]+v[i])
pp[i][j]: 전 i개 아이템 총 중량이 j를 초과하지 않는 아이템 시 총 가치의 최대치
(i 순서, j 순서)
i:1~n j:0~W
★ 초기화 dp[0][j]=0(dp[i-1][j]상태일 때 사용되며 i=0일 경우 아이템을 선택하지 않은 것과 같다)
1. 남은 아이템이 없습니다(i>n)
2. 이 아이템을 고를 수 없다(j)
3. 선택 여부를 선택할 수 있다면(dp[i][j]=max(dp[i-1][j], dp[i-1][j-w[i]]]+v[i])
엔트리: HDU 2602

#include 
#include 
#include 
#include 
using namespace std;
const int N = 1e3 + 10;
int dp[N][N];
int w[N], v[N];
int main() {
	int t;
	scanf("%d", &t);
	while(t--) {
		memset(dp, 0, sizeof(dp));
		int n, V;
		scanf("%d %d", &n, &V);
		for(int i = 1; i <= n; i++) {
			scanf("%d", &v[i]);
		}
		for(int i = 1; i <= n; i++) {
			scanf("%d", &w[i]);
		}
		for(int i = 1; i <= n; i++) {
			for(int j = 0; j <= V; j++){
				if(j < w[i]){
					dp[i][j] = dp[i - 1][j];
				}
				else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
			}
		}
		printf("%d
", dp[n][V]);



	}
}

최대 공통 하위 시퀀스(LCS)
s1~sn  t1~tn
dp[i][j] :s1...si와 t1...tj의 LCS 길이
s1...si+1과 t1...ti+1에 대응하는 공통 하위 서열은
si+1=ti+1 시, s1...si와 t1...tj의 LCS 끝에si+1 추가
    s1..si와 t1...tj+1 LCS
    s1..si+1과 t1...tj용 LCS
dp[i+1][j+1]=dp[i][j]+1(si+1=tj+1)
=max(dp[i][j+1], dp[i+1][j])(기타)
POJ 1458

#include 
#include 
#include 
#include 
using namespace std;
const int N = 1e3 + 10;
char s[N], t[N];
int dp[N][N];
int main(){
	while(~scanf("%s %s", s, t)){
		memset(dp, sizeof(dp), 0);
		int n = strlen(s);
		int m = strlen(t);
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				if(s[i] == t[j]){
					dp[i+1][j+1] = dp[i][j] + 1;
				}
				else{
					dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
				}
			}
		}
		printf("%d
", dp[n][m]);
	}
} 

완전 배낭
pp[i][j]: 전 i개 아이템 총 중량이 j를 초과하지 않는 아이템 시 총 가치의 최대치
dp[0][j]=0
i:1~n j:0~W k:0~k*w[i]
dp[i][j]=max(dp[i][j], dp[i-1][j-k*w[i]]+k*v[i])(dp[i][j]는 k순환 때문)O(nW2)
그러나 dp[i][j]에서 k개를 선택한 경우 dp[i][j-w[i]에서 k-1개를 선택하여 계산한 경우(w[i]가 바로 k개)
즉 dp[i][j]가 점차적으로 k≥1을 미루는 상황은 이미 계산되었다
따라서 변형할 수 있다
max{dp[i-1][j-k*w[i]]+k*v[i](k≥0)}
=max(dp[i-1][j],max｛dp[i-1][j-k*w[i]]+k*v[i](k≥1)｝)
=max(dp[i-1][j],max { dp[i-1][( j-w[i]) - k*w[i]]+k*v[i](k≥0)}+v[i])
=max(dp[i-1][j],dp[i][j-w[i]]+v[i])
dp[i][j]=dp[i-1][j](jO(nW)
          =max(dp[i-1][j],dp[i][j-w[i]]+v[i])
본질은 현재 상태에서 k개를 선택할 때, 현재 k-1개를 선택한 상태에서 직접 이동합니다
엔트리: HDU 1248

#include 
#include 
#include 
#include 
using namespace std;
const int N = 1e4 + 10;
int dp[5][N];
int main(){
	int w[4] = {0, 150, 200, 350};
	int t,W;
	scanf("%d", &t);
	while(t--){
		memset(dp, 0, sizeof(dp));
		scanf("%d", &W);
		for(int i = 1; i <= 3; i++){
			for(int j = 0; j <= W ;j++){
				if(j < w[i]){
					dp[i][j] = dp[i - 1][j];
				}
				else dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + w[i]);
			}
		}
		printf("%d
", W - dp[3][W]);
	}
}

1차원 그룹의 실현 (공간 복잡도 감소)
01 가방:
    i:1~n j:
W~w[i] dp[j]=max(dp[j],dp[j-w[i]]+v[i])
전체 가방:
    i:1~n j:
w[i]~W dp[j]=max(dp[j],dp[j-w[i]]+v[i])
★ 순환하는 방향만 다르다
다중 섹션 및 질문:
ai mi K
pp[i+1][j]: 전 i종수로 j를 더하고 얻었을 때 i종수는 최대 몇 개의 O(nK)를 남길 수 있습니까
1. 앞에 이미 jdp[i+1][j]=m[i]dp[i][j]≥0
2. 추가할 수 없는 상황: 현재 a[i]>j 또는 전 i+1개수가 j-a[i]에 추가되었을 때 이미 남은 dp[i+1][j-a[i]]≤0
3. 앞에 이미 j-a[i]까지 추가되었는데 여기에 a[i]가 하나 더 필요합니다.
dp[i+1][j]=dp[i+1][j-a[i]]-1
+ 배열 재사용:

 
     
 
      
int dp[MAX_K + 1];
 
      
 
      
void solve() {
 
      
 memset(dp, -1, sizeof(dp));
 
      
 dp[0] = 0;
 
      
 for (int i = 0; i < n; i++){
 
      
 for (int j = 0; j < W; j++){
 
      
 if (dp[j] >= 0) dp[j] = m[i];
 
      
 else if (j < a[i] || dp[j - a[i]] <= 0) dp[j] = -1;
 
      
 else dp[j] = dp[j - a[i]] - 1;
 
      
 }
 
      
 }
 
      
 if(dp[K] >= 0) puts("YES");
 
      
 else puts("NO");
 
      
}
 
     
 
    

（LIS）

a[i] n

dp[i]: i （ ）  O(nlogn)

j:1~n i:1~n

INF

1.  j==1 dp[i]=a[j]

2. dp[i-1]a[j]>dp[i-1]의 위치를 찾으면 현재 위치의 dp[i]를min(dp[i], a[i])으로 바꿉니다.

n ² nlogn

*lower_bound(dp,dp+n,a[i]) ai _-1i≤a i+1

*upper_bound: a _i-1<=a _ii+1 

：HDU 5748

#include 
#include 
#include 
#include 
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int a[N], b[N];
int dp[N];
int main(){
	int t;
	scanf("%d", &t);
	while (t--){
		int n;
		scanf("%d", &n);
		memset(dp, INF, sizeof(dp));
		for (int i = 1; i <= n; i++){
			scanf("%d", &a[i]);
		}
		for (int i = 1; i <= n; i++){
			*lower_bound(dp, dp + n, a[i]) = a[i];
			b[i]=lower_bound(dp, dp + n, a[i]) - dp + 1;
		}
		
	
		for (int i = 1; i < n; i++){
			printf("%d ", b[i]);	
		}
		printf("%d
", b[n]);
		
	
	}
}

， b[i]， LIS(b[i])=a[i] b[i] ， LIS。

lower_bound

lower_bound upper_bound 。

dp：

：n m

dp[i][j]:j i

1）

2） -1；

 
      
 
       
int f(int n,int idx){  
   if(n==0) return 1;     if(idx<=0) return 0;     return f(n-idx,idx)+f(n,idx-1);    }     
i:1~n j:1~m 
dp[i][j]=dp[i-j][j]+dp[i][j-1] (O(nm)) 
다중 집합 조합수: n가지 아이템 각종ai개(종류별 아이템 동일) m개 추출
dp[i+1][j]: 이전 i종 아이템에서 j종을 추출하는 방안수
모든 dp[i+1][j]는 이전 i-1종의 물품에서 물건을 가져와 dp[i][j-0]+dp[i][j-1]+...+dp[i][j-min(ai,j)] 
dp[i+1][j]= 
dp[i][j-0]+dp[i][j-1]+...+dp[i][j-min(ai,j)]=dp[i][j]+dp[i][j-1]+dp[i][j-1-1]+dp[i][j-1-2]+...+dp[i][j-1-(min(ai,j)-1)] 
=dp[i][j]+dp[i+1][j-1]-dp[i][j-1-min(ai,j)] 
i:0~n 
j:0~m 
제목: POJ 3046