ຜົນລວມຂອງເສັ້ນທາງສູງສຸດໃນສາມຫຼ່ຽມ


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Arcesium CodeNation GE Healthcare PayU Uber Zoho
ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ

ຖະແຫຼງການບັນຫາ

ບັນຫາ“ ຍອດລວມຂອງເສັ້ນທາງສູງສຸດໃນສາມຫຼ່ຽມ” ລະບຸວ່າທ່ານໄດ້ຮັບ ຈຳ ນວນ ໜຶ່ງ ເທົ່ານັ້ນ. ເລກເຕັມເຫລົ່ານີ້ຖືກຈັດເປັນຮູບສາມຫລ່ຽມ. ທ່ານ ກຳ ລັງເລີ່ມຕົ້ນຈາກດ້ານເທິງຂອງສາມຫຼ່ຽມແລະຕ້ອງການທີ່ຈະໄປເຖິງແຖວລຸ່ມ. ສໍາລັບການເຮັດສິ່ງນີ້, ທ່ານຍ້າຍໄປຢູ່ໃນຈຸລັງທີ່ຢູ່ຕິດກັນໃນແຖວຕໍ່ໄປ. ສະນັ້ນເມື່ອທ່ານ ກຳ ລັງເຄື່ອນຍ້າຍສາມຫລ່ຽມໃນລັກສະນະທີ່ ກຳ ນົດ, ຈຳ ນວນເງິນສູງສຸດທີ່ທ່ານສາມາດບັນລຸໄດ້ແມ່ນຫຍັງ?

ຍົກຕົວຢ່າງ

ຜົນລວມຂອງເສັ້ນທາງສູງສຸດໃນສາມຫຼ່ຽມ

  1
 2 3
5 8 1
12

ຄໍາອະທິບາຍ
ທ່ານພຽງແຕ່ສາມາດເລື່ອນເສັ້ນທາງໃນລັກສະນະດັ່ງຕໍ່ໄປນີ້. 1-> 3-> 8, ເສັ້ນທາງນີ້ຈະເຮັດໃຫ້ທ່ານບັນລຸຍອດລວມສູງສຸດທີ່ 12.

ວິທີການ

ດັ່ງນັ້ນພວກເຮົາຈະສາມາດແກ້ບັນຫາເສັ້ນທາງສູງສຸດໃນສາມຫຼ່ຽມໄດ້ແນວໃດ? ຈົນກ່ວາໃນປັດຈຸບັນ, ພວກເຮົາມີຫຼາຍຄຸ້ນເຄີຍກັບບັນຫາປະເພດເຫຼົ່ານີ້. ທຸກຄັ້ງທີ່ພວກເຮົາໄດ້ຮັບການສະ ໜອງ ໃຫ້ກັບບັນຫາປະເພດນີ້. ວິທີການບັງຄັບໃຊ້ຢ່າງສະ ໝ ່ ຳ ສະ ເໝີ ແມ່ນການສ້າງທຸກວິທີທາງທີ່ເປັນໄປໄດ້ເພື່ອບັນລຸຈຸດ ໝາຍ ຂອງທ່ານ. ແລະຫຼັງຈາກນັ້ນສືບຕໍ່ປັບປຸງ ຄຳ ຕອບ ສຳ ລັບຜົນໄດ້ຮັບທີ່ດີທີ່ສຸດ, ໂດຍການຄິດໄລ່ຜົນລວມ ສຳ ລັບແຕ່ລະເສັ້ນທາງ. ແຕ່ວິທີການນີ້ບໍ່ມີປະສິດທິພາບສູງເພາະວິທີການນີ້ຮຽກຮ້ອງໃຫ້ພວກເຮົາສ້າງເສັ້ນທາງ. ແລະພວກເຮົາຮູ້ວ່າການຜະລິດເສັ້ນທາງແມ່ນວຽກທີ່ມີຄວາມສັບສົນທີ່ໃຊ້ເວລາເຊິ່ງບໍ່ແມ່ນສິ່ງທີ່ດີ.

ສະນັ້ນ, ເພື່ອແກ້ໄຂບັນຫານີ້ພວກເຮົາຕ້ອງຄິດຫາວິທີອື່ນ. ຈາກນັ້ນ ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ ມາກູ້ໄພຂອງພວກເຮົາ. ເນື່ອງຈາກວ່າແທນທີ່ຈະຜະລິດເສັ້ນທາງ, ຖ້າພວກເຮົາສາມາດຮູ້ບາງສິ່ງບາງຢ່າງທີ່ສູງສຸດທີ່ສາມາດບັນລຸໄດ້ຈາກຫ້ອງເພື່ອບັນລຸແຖວລຸ່ມ. ວິທີນັ້ນພວກເຮົາສາມາດໄດ້ຮັບຜົນ ສຳ ລັບຫ້ອງທີ່ຕິດກັບມັນແຕ່ຕິດຕໍ່ກັນຢູ່ຂ້າງແຖວນັ້ນ. ສະນັ້ນ, ພວກເຮົາໃຊ້ DP ເພື່ອແກ້ໄຂບັນດາເຄື່ອງ ໝາຍ ຍ່ອຍນ້ອຍກວ່າ. ຫຼັງຈາກນັ້ນ, ສົມທົບຜົນໄດ້ຮັບ ສຳ ລັບເຄື່ອງ ໝາຍ ຍ່ອຍເຫຼົ່ານັ້ນພວກເຮົາພົບ ຄຳ ຕອບ ສຳ ລັບບັນຫາເດີມ.

ຫນ້າທໍາອິດ, ພວກເຮົາຕື່ມຄໍາຕອບສໍາລັບຈຸລັງຢູ່ໃນແຖວສຸດທ້າຍ. ພວກເຮົາຮູ້ວ່າຜົນລວມສູງສຸດທີ່ສາມາດບັນລຸໄດ້ຖ້າພວກເຮົາເລີ່ມຕົ້ນຈາກຈຸລັງຢູ່ແຖວລຸ່ມແມ່ນຕົວເລກຕົວມັນເອງ. ຫລັງຈາກນັ້ນ, ພວກເຮົາຍ້າຍໄປແຖວແຖວເທິງແຖວລຸ່ມ. ສຳ ລັບແຕ່ລະຫ້ອງທີ່ຢູ່ໃນແຖວປະຈຸບັນ, ພວກເຮົາສາມາດເລືອກຄ່າ DP ຂອງຄ່າຂອງຈຸລັງທີ່ຢູ່ຕິດກັນກັບມັນຢູ່ໃນແຖວຢູ່ທາງລຸ່ມຂອງມັນ. ວິທີນີ້ພວກເຮົາສືບຕໍ່ເດີນໄປໃນທິດທາງທີ່ສູງຂຶ້ນ. ເມື່ອພວກເຮົາໄປຮອດແຖວສຸດ, ພວກເຮົາກໍ່ປະຕິບັດກັບບັນຫາ.

ລະຫັດ C ++ ເພື່ອຊອກຫາຍອດລວມເສັ້ນທາງສູງສຸດໃນສາມຫຼ່ຽມ

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int maximumPathSumInTriangle(vector<vector<int>> &input)
{
    int n = input.size();
    // start from row above bottom row
    // since the bottom row cells are the answers themselves
  for(int i=n-2;i>=0;i--)
  {
      // start from left to right in column
    for(int j=0;j<=i;j++)
    {
      if(input[i+1][j] > input[i+1][j+1])
        input[i][j] += input[i+1][j];
      else
        input[i][j] += input[i+1][j+1];
    }
  }
  return input[0][0];
}

int main()
{
    int n;cin>>n; // number of rows
    vector<vector<int>> input(n, vector<int>(n, 0));
    for(int i=0;i<n;i++){
        for(int j=0;j<=i;j++)
            cin>>input[i][j];
    }
    cout<<maximumPathSumInTriangle(input);
}

}
3
1
2 3
5 8 1
12

ລະຫັດ Java ເພື່ອຊອກຫາຜົນລວມເສັ້ນທາງສູງສຸດໃນສາມຫຼ່ຽມ

import java.util.*;

class Main{
  static int maximumPathSumInTriangle(int input[][], int n)
  {
      // start from row above bottom row
      // since the bottom row cells are the answers themselves
    for(int i=n-2;i>=0;i--)
    {
        // start from left to right in column
      for(int j=0;j<=i;j++)
      {
        if(input[i+1][j] > input[i+1][j+1])
          input[i][j] += input[i+1][j];
        else
          input[i][j] += input[i+1][j+1];
      }
    }
    return input[0][0];
  }

  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt(); // number of rows
      int input[][] = new int[n][n];
      for(int i=0;i<n;i++){
          for(int j=0;j<=i;j++)
              input[i][j] = sc.nextInt();
      }
      int answer = maximumPathSumInTriangle(input, n);
      System.out.print(answer);
  }
}
3
1
2 3
5 8 1
12

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

O (N ^ 2), ດັ່ງທີ່ພວກເຮົາຍ້າຍຜ່ານແຕ່ລະແຖວແລະແຕ່ລະຖັນ. ໃນຂັ້ນຕອນ, ພວກເຮົາໄດ້ເດີນທາງໄປແຕ່ລະຫ້ອງ. ແລະເນື່ອງຈາກວ່າມີຈຸລັງ O (N ^ 2) ຢູ່ໃນສາມຫຼ່ຽມແລະການຫັນປ່ຽນ ສຳ ລັບ DP ໃຊ້ເວລາປະຕິບັດງານ O (1) ເທົ່ານັ້ນ. ດັ່ງນັ້ນ, ຄວາມສັບສົນຂອງເວລາກໍ່ຍັງມີຫຼາຍຮູບແບບເຊັ່ນກັນ.

ຄວາມສັບສົນໃນອະວະກາດ

O (N ^ 2) ນັບຕັ້ງແຕ່ພວກເຮົາສ້າງ 2D DP array. ດັ່ງນັ້ນຄວາມສັບສົນໃນພື້ນທີ່ຍັງມີຫຼາຍຮູບແບບ.