C++에서 파스칼의 삼각형 II

k ≤ 33인 음수가 아닌 인덱스 k가 있다고 가정하면 파스칼 삼각형의 k번째 인덱스 행을 찾아야 합니다.

따라서 입력이 3과 같으면 출력은 [1,3,3,1]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• rowIndex + 1 크기의 배열 파스칼을 정의하고 0으로 채웁니다.

• 초기화 r :=0의 경우, r <=rowIndex일 때 업데이트(r을 1만큼 증가), -

  수행

  • 파스칼[r] :=1, 이전 :=1

  • initialize i :=1의 경우, i

    • cur :=파스칼[i]

    • 파스칼[i] :=파스칼[i] + 이전

    • 이전 :=현재

• 리턴 파스칼

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int> getRow(int rowIndex) {
      vector<int> pascal(rowIndex + 1, 0);
      int prev, cur, r, i;
      for (r = 0; r <= rowIndex; r++) {
         pascal[r] = prev = 1;
         for (i = 1; i < r; i++) {
            cur = pascal[i];
            pascal[i] += prev;
            prev = cur;
         }
      }
      return pascal;
   }
};
main(){
   Solution ob;
   print_vector(ob.getRow(3));
}

입력

3

출력

[1, 3, 3, 1, ]