(1932) 정수 삼각형

https://www.acmicpc.net/problem/1932

단계별로 풀어보기

21단계(동적 계획법 1) 7번째

 

 

 

dp[a][b]를 a층의 b번째 숫자에 도달했을 때 최댓값이라고 하면 현재 숫자에 dp[a-1][b-1]과 dp[a-1][b] 중 큰 값을 더한 것과 같다. (단 b=0이면 항상 dp[a-1][b]이고 b=a면 항상 dp[a-1][b-1]임)

이전 문제와 마찬가지로 a층의 dp값을 구할 때 필요한 것은 a-1층의 dp값 뿐이므로 메모리를 절약할 수 있다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector<int> v(n), dp(n);
  
  cin >> v[0];
  dp[0]= v[0];
  
  for(int i=1;i<n;i++){
    for(int j=0;j<=i;j++)  cin >> v[j];
    
    v[0]+= dp[0];  v[i]+= dp[i-1];
    for(int j=1;j<i;j++)  v[j]+= max(dp[j-1], dp[j]);
    
    dp= v;
  }
  
  cout << *max_element(dp.begin(), dp.end());
  
  return 0;
}