알고리즘 도론 15장 동적 기획
public class Main {
int n = 10;
int[] p = new int[]{1,5,8,9,10,17,17,20,24,30};
int[] r = new int[n+1];
int[] s = new int[n+1];
int solve(int n,int[] s,int c){
if(n==0) return 0;
if(r[n]>=0) return r[n];
else{
int max = -10000;
for(int i=1;i<=n;i++){
int t = p[i-1]+solve(n-i,s,c)-c;
if(t>max){
max = t;
s[n] = i;
}
}
r[n] = max;
return max;
}
}
void solve2(int n){
Arrays.fill(r, -1);
r[0] = 0;
for(int i=1;i<=n;i++){
int max = 0;
for(int j=1;j<=i;j++){
if(max<p[j-1]+r[i-j]){
max = p[j-1]+r[i-j];
s[i] = j;
}
}
r[i] = max;
}
System.out.println(" "+r[n]);
System.out.println(" :");
while(n>0){
System.out.println(s[n]);
n = n-s[n];
}
}
public static void main(String[] args) {
Main m = new Main();
Arrays.fill(m.r, -1);
System.out.println(m.solve(7,m.s,1));
System.out.println(Arrays.toString(m.s));
int n = 7;
while(n>0){
System.out.println(m.s[n]);
n = n-m.s[n];
}
}
}
행렬 곱하기
최대 공통 하위 시퀀스
public class Main {
int n = 6;
int[][] m = new int[n][n];
int[][] s = new int[n][n];
int solve(int[] p){
for(int i=0;i<n;i++){
m[i][i] = 0;
}
for(int l=1;l<n;l++){//l-1
for(int i=0;i<n-l;i++){//i
int j = i+l;//j
m[i][j] = 100000;
for(int k=i;k<j;k++){//k
if(m[i][j]>m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1]){
m[i][j]=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1];
s[i][j] = k;
}
}
}
}
return m[0][n-1];
}
int solve(int[] p,int i,int j){
if(m[i][j]>0) return m[i][j];
if(i==j) return 0;
m[i][j] = 100000;
for(int k=i;k<j;k++){
int t = solve(p, i, k)+solve(p,k+1,j)+p[i]*p[k+1]*p[j+1];
if(m[i][j]>t){
m[i][j] = t;
s[i][j] = k;
}
}
return m[i][j];
}
void print(int[][] s,int i,int j){
if(i==j){
System.out.print("A"+i);
}else{
System.out.print('(');
print(s, i, s[i][j]);
print(s, s[i][j]+1,j);
System.out.print(')');
}
}
public static void main(String[] args) {
Main m = new Main();
//System.out.println(m.solve(new int[]{5,10,3,12,5,50,6}));
//m.print(m.s,0,5);
System.out.println(m.solve(new int[]{5,10,3,12,5,50,6},0,5));
m.print(m.s,0,5);
}
}
최장 단조 증가 서브 시퀀스
public class Main {
void solve(char[] x,char[] y){
int m = x.length;
int n = y.length;
int c[][] = new int[m+1][n+1];
for(int i=0;i<n;i++){
c[0][i] = 0;
}
for(int i=0;i<m;i++){
c[i][0] = 0;
}
for(int i=1;i<=m;i++){//i
for(int j=1;j<=n;j++){//j
if(x[i-1]==y[j-1]){
c[i][j] = c[i-1][j-1]+1;
}else{
c[i][j] = Math.max(c[i][j-1], c[i-1][j]);
}
}
}
System.out.println(c[m][n]);
print(c, m, n, x);
}
int solve2(int c[][],char[] x,char[] y,int i,int j){
if(c[i][j]>0) return c[i][j];
if(i==0||j==0) c[i][j] = 0;
else{
if(x[i-1]==y[j-1]){
c[i][j] = solve2(c, x, y, i-1, j-1)+1;
}else{
c[i][j] = Math.max(solve2(c, x, y, i-1, j), solve2(c, x, y, i, j-1));
}
}
return c[i][j];
}
void print(int[][] c,int m,int n,char[] x){
if(m==0||n==0) return;
if(c[m][n]==c[m-1][n-1]+1){
System.out.println(x[m-1]);
print(c, m-1, n-1, x);
}else if(c[m][n]==c[m-1][n]){
print(c, m-1, n, x);
}else{
print(c, m, n-1, x);
}
}
public static void main(String[] args) {
Main m = new Main();
//m.solve("BDCABA".toCharArray(),"ABCBDAB".toCharArray());
char[] a1 = "BDCABA".toCharArray();
char[] a2 = "ABCBDAB".toCharArray();
int[][] c = new int[a1.length+1][a2.length+1];
int t = m.solve2(c, a1, a2, a1.length, a2.length);
System.out.println(t);
m.print(c, a1.length, a2.length, a1);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.