ເສັ້ນທາງ Sum ຂັ້ນຕ່ ຳ ສຸດໃນສາມຫຼ່ຽມ


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Amazon ຈາກຫນາກແອບເປີ Bloomberg
Array ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ

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

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

ຍົກຕົວຢ່າງ

ເສັ້ນທາງ Sum ຂັ້ນຕ່ ຳ ສຸດໃນສາມຫຼ່ຽມ

  1
 2 3
5 8 1
5

ຄໍາອະທິບາຍ
ທ່ານພຽງແຕ່ສາມາດເລື່ອນເສັ້ນທາງໃນລັກສະນະດັ່ງຕໍ່ໄປນີ້. 1-> 3-> 1. ດັ່ງນັ້ນ ຈຳ ນວນດັ່ງກ່າວແມ່ນ 5. ຖ້າພວກເຮົາຈະມີວິທີການທີ່ໂລບມາກ. ພວກເຮົາອາດຈະໄດ້ກັບ 2 ແທນທີ່ຈະເປັນຂອງ 3. ດັ່ງນັ້ນພວກເຮົາສາມາດຈົບລົງດ້ວຍພຽງ 8 ຫລື 11 ເຊິ່ງສູງກວ່າ 5.

ວິທີການ

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

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

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

ລະຫັດ C ++ ເພື່ອຊອກຫາ ຕຳ ແໜ່ງ ເສັ້ນທາງ ຕຳ ່ສຸດໃນສາມຫຼ່ຽມ

#include<bits/stdc++.h>
using namespace std;
int minimumPathSumInTriangle(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<<minimumPathSumInTriangle(input);
}
3
1
2 3
5 8 1
5

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

import java.util.*;
class Main{
  static int minimumPathSumInTriangle(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 = minimumPathSumInTriangle(input, n);
      System.out.print(answer);
  }
}
3
1
2 3
5 8 1
5

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

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

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

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

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