[백준] 11722: 가장 긴 감소하는 부분 수열 - Java (DP)

목 차 문제 접근 방식 풀이 문제 접근 방식 가장 긴 증가하는 부분 수열에서는 Bottom-up 방식이 합리적이었다. 그래서 감소하는 부분 수열에서는 반대로 Top-down 방식으로 해서 같은 방식으로 풀어주었다. 포인터 i 와 포인터 j 를 가진다. 둘의 초기값은 arr.length - 1 이다. 그리고 i를 기준으로 하나씩 확인하면서 만약 i 보다 작다면 dp[i] = dp[j] + 1; 을 해준다. 우리는 j를 통해서 반복적으로 확인을 해야하다 보니 Math.max() 로 감싸준다. 점화식이다. if(arr[i] > arr[j]){ dp[i] = Math.max(dp[j] + 1, dp[i]); } 조건문은 코드마다 달라질 수 있겠지만 그 안에 점화식은 큰 변화는 없을 거다. 풀이 package s..

Algorithm 2024.01.22