dp

조건

dag일 때 사용

11048번: 이동하기

점화식은 세우니 나름이다

dp[i][j] := (i, j)에서 시작해서 (N, M)에 도착할 때, 최대값
dp[i][j] := (1, 1)에서 시작해서 (i, j)에 도착할 때, 최대값
등등

아래는 첫 번째 dp 정의를 이용한 풀이이다.

#include <bits/stdc++.h>
#define endl '\n' // don't use when you cover interactive problem
#define MAX 1001
#define NON -1
 
using namespace std;
 
int N, M;
int d[MAX][MAX];
int dp[MAX][MAX]; // dp[i][j] := (i, j)에서 시작해서 (N, M)에 도착할 때, 최대값
 
int go(int r, int c)
{
    if(r > N || c > M) return 0;
    if(dp[r][c] != NON) return dp[r][c];
 
    int ret = max(go(r+1, c), go(r, c+1)) + d[r][c];
    return dp[r][c] = ret;
}
 
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
 
    cin >> N >> M;
    for(int r = 1; r <= N; r++){
        for(int c = 1; c <= M; c++) {
            cin >> d[r][c];
            dp[r][c] = NON;
        }
    }
 
    cout << go(1, 1) << endl;
 
    return 0;
}cs

 

 

코딩 스타일

• input 노드에 주목해서 코딩
  • bottom-up

  #include <bits/stdc++.h>
  #define endl '\n' // don't use when you cover interactive problem
  #define MAX 1001
   
  using namespace std;
   
  int N, M;
  int d[MAX][MAX];
  int dp[MAX][MAX]; // dp[i][j] := (1, 1)에서 시작해서 (i, j)에 도착할 때, 최대값
   
  int main() {
      ios::sync_with_stdio(false), cin.tie(0);
   
      cin >> N >> M;
      for(int r = 1; r <= N; r++){
          for(int c = 1; c <= M; c++) cin >> d[r][c];
      }
   
      dp[1][1] = d[1][1];
      for(int r = 1; r <= N; r++){
          for(int c = 1; c <= M; c++){
              dp[r][c] = max({dp[r-1][c], dp[r][c-1], dp[r-1][c-1]}) + d[r][c];
          }
      }
      cout << dp[N][M] << endl;
   
      return 0;
  }cs

  • top-down(메모이제이션 해야 함, 이때 배열은 답으로 절대 나올 수 없는 값으로 초기화. 그렇지 않으면 메모이제이션이 의미가 없어지는 경우가 있음)
    메모이제이션 값을 return 하기 전에 유효한 index 인지 확인해야 함
    (base 조건에서는 dp 배열의 크기를 넘어서는 index에 대한 호출이 일어날 수도 있음)

    

    19번 코드에 ind, dep이 유효하지 않으면 UB라서 지옥의 디버깅이 펼쳐진다

  #include <bits/stdc++.h>
  #define endl '\n' // don't use when you cover interactive problem
  #define MAX 1001
  #define NON -1
   
  using namespace std;
   
  int N, M;
  int d[MAX][MAX];
  int dp[MAX][MAX]; // dp[i][j] := (1, 1)에서 시작해서 (i, j)에 도착할 때, 최대값
   
  int go(int r, int c)
  {
      if(r < 1 || c < 1) return 0;
      if(dp[r][c] != NON) return dp[r][c];
   
      int ret = max(go(r-1, c), go(r, c-1)) + d[r][c];
      return dp[r][c] = ret;
  }
   
  int main() {
      ios::sync_with_stdio(false), cin.tie(0);
   
      cin >> N >> M;
      for(int r = 1; r <= N; r++){
          for(int c = 1; c <= M; c++) {
              cin >> d[r][c];
              dp[r][c] = NON;
          }
      }
   
      cout << go(N, M) << endl;
   
      return 0;
  }cs

 

• output 노드에 주목해서 코딩(bottom up)

#include <bits/stdc++.h>
#define endl '\n' // don't use when you cover interactive problem
#define MAX 1001
 
using namespace std;
 
int N, M;
int d[MAX][MAX];
int dp[MAX][MAX]; // dp[i][j] := (1, 1)에서 시작해서 (i, j)에 도착할 때, 최대값
 
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
 
    cin >> N >> M;
    for(int r = 1; r <= N; r++){
        for(int c = 1; c <= M; c++) cin >> d[r][c];
    }
 
    dp[1][1] = d[1][1];
    for(int r = 1; r <= N; r++){
        for(int c = 1; c <= M; c++){
            if(r+1 <= N) dp[r+1][c] = max(dp[r+1][c], dp[r][c] + d[r+1][c]);
            if(c+1 <= M) dp[r][c+1] = max(dp[r][c+1], dp[r][c] + d[r][c+1]);
            if(r+1 <= N && c+1 <= M) dp[r+1][c+1] = max(dp[r+1][c+1], dp[r][c] + d[r+1][c+1]); // 사실 이 줄은 필요 없음
        }
    }
    cout << dp[N][M] << endl;
 
    return 0;
}cs

 

팁

• 주어진 연산을 적용했을 때 소문제(그 부분만 따로 testcase로 제시하여도 원래 문제와 목표, 제한 등이 같은 문제. 그러니까 문제의 크기가 작아진 또 다른 testcase로 받아들여지는 문제)로 변하면 dp를 적용해보자
• 배열 내부에서 arr[i...j] 와다다 뭔가 일어나면 2차원 dp일 수 있음
• 단계별로 값이 변하면 그 단계별로 값을 저장하는 dp일 수 있음