C++디지털 삼각형 문제 와 dp 알고리즘

제목:숫자 삼각형
제목 소개:그림 에서 보 듯 이 디지털 삼각형 은 맨 위 정점 부터 한 걸음 한 걸음 씩 맨 밑 으로 내 려 가 야 한다.모든 단 계 는 반드시 다음 층 으로 내 려 가 거 친 숫자의 최대 화 를 구 해 야 한다.
입력:첫 번 째 줄 값 n 은 n 줄 수 치 를 대표 합 니 다.뒤의 n 줄 데 이 터 는 각 줄 의 숫자 를 대표 합 니 다.
출력:숫자의 최대 합 을 거 칩 니 다.
예:

입력:
4
1
3 2
4 10 1
4 3 2 20
출력:
24
분석:이것 도 전형 적 인 욕심 산법 으로 해결 할 수 없 는 문제 이 고 동적 계획(dp 알고리즘)으로 해결 할 수 있다.경계 숫자 를 먼저 결과 행렬 로 초기 화하 고 상태 방정식 에 따라 결과 행렬 의 역 주 행 을 완성 합 니 다.주의해 야 할 것 은 배열 이 직사각형 이 아니 라 삼각형 이 므 로 전통 적 인 상태 방정식 에 비해 개선 이 필요 하 다 는 것 이다.
배열 번호:

상태 방정식:p[ i ][ j ]=max{ p[ i-1 ][ j-1 ] , p[ i-1 ][ j ]}코드 는 다음 과 같 습 니 다:

#include <iostream>
using namespace std;
int main()
{
  int i;
  int n;
  cin >> n;
  int **p = new int *[n];
  for (i = 0; i < n; i++)
  {
    p[i] = new int[n];
  }
  for (i = 0; i < n; i++)
  {
    for (int j = 0; j <= i; j++)
    {
      cin >> p[i][j];
    }
  }
  for (i = 1; i < n; i++)
  {
    p[i][0] += p[i - 1][0];
  }
  for (i = 1; i < n; i++)
  {
    p[i][i] += p[i - 1][i - 1];
  }
  for (i = 2; i < n; i++)
  {
    for (int j = 1; j < i; j++)
    {
      p[i][j] += (p[i - 1][j - 1] > p[i - 1][j]) ? p[i - 1][j - 1] : p[i - 1][j];
    }
  }
  for (i = 0; i < n; i++)
  {
    for (int j = 0; j <= i; j++)
    {
      cout << p[i][j] << " ";
    }
    cout << endl;
  }
}
결 과 는 다음 그림 과 같다.

그래서 최 하층 의 숫자 와 최대 치 는 24 입 니 다.
총결산
위 에서 말 한 것 은 소 편 이 여러분 에 게 소개 한 C++디지털 삼각형 문제 와 dp 알고리즘 입 니 다.여러분 에 게 도움 이 되 기 를 바 랍 니 다.궁금 한 점 이 있 으 시 면 저 에 게 메 시 지 를 남 겨 주세요.소 편 은 제때에 답 해 드 리 겠 습 니 다!

좋은 웹페이지 즐겨찾기