DP 문제 풀이 유형

1. 가장 ~~ 한 부분 수열 구하기 유형

 

2중 for문을 돌면서 조건에 따라 dp 값을 갱신한다.

  for (int i = 1; i <= n; i++)
  {
    dp[i] = 1;
    for (int j= 1; j<i; j++)
    {
      if (arr[i] > arr[j])
      {
        dp[i] = max(dp[i], dp[j]+1);
      }
    }
  }

2. 냅색 문제

 

이어 적어보자.