알고리즘) 행렬 곱셈 &다양한 dp문제풀이들

 

---

 

 

 

 

 

 

 

 

 

부분합은 "연속"되어야 합니다 (끊기면 안 됨)

부분합은 배열에서 숫자들을 건너뛸 수 없습니다. 만약 배열이 [-2000, 100, -5000] 이라면:

• 우리가 원하는 진짜 최솟값은 아마도 -2000 + 100 + (-5000) = -6900일 것입니다.
• 이 -6900이라는 값을 얻으려면, 중간에 있는 100이 꼴 보기 싫어도 꾹 참고 더하면서 지나가야만 저 뒤에 있는 대박 음수 -5000을 만날 수 있습니다.
• 만약 100이 크다고 여기서 멈춰버리면, 뒤에 뭐가 있든 상관없이 그냥 -2000에서 끝나는 거죠.

 

 

 

 

 

 

삼각형 부분 가우스 더하기인 이유(선으로 둘러싸인 매끈한 삼각형이 아님)

1+2+3+4...+k니깐 결국 

 

 

 

 

직사각형 구간 

 

 

 

 

 

 

 

 

 

그림보면 
 

1. B[i-1][j-1]: 내 위치에서 바로 윗줄, 한 칸 왼쪽에 있는 숫자
2. B[i-1][j]: 내 위치에서 바로 윗줄, 내 머리 위에 있는 숫자

즉, **"바로 위 숫자 + 그 왼쪽 숫자"**를 더해서 내 칸을 채우는 것입니다
 
 
 

 
 

 
 

 
 
 
 

---