ຜົນບວກຕ່ ຳ ສຸດຂອງການຄູນເລກຂອງ ຈຳ ນວນ n


ລະດັບຄວາມຫຍຸ້ງຍາກ Hard
ຖາມເລື້ອຍໆໃນ Accenture BlackRock GE Healthcare JP Morgan PayPal
Array ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ

ບັນຫາ“ ຜົນບວກຕ່ ຳ ສຸດຂອງການຄູນເລກຂອງ ຈຳ ນວນ n” ລະບຸວ່າທ່ານຖືກມອບໃຫ້ n integers ແລະທ່ານຕ້ອງການຫຼຸດຜ່ອນຜົນບວກຂອງຕົວເລກທັງ ໝົດ ໃຫ້ ໜ້ອຍ ທີ່ສຸດໂດຍການເອົາສອງອົງປະກອບທີ່ຢູ່ຕິດກັນໃນແຕ່ລະຄັ້ງແລະວາງ ຈຳ ນວນ sum ຂອງພວກເຂົາ 100 ຈົນກວ່າຈະມີຕົວເລກດຽວ.

ຍົກຕົວຢ່າງ

ຜົນບວກຕ່ ຳ ສຸດຂອງການຄູນເລກຂອງ ຈຳ ນວນ n

10 20 30
1100

ຄໍາອະທິບາຍ

ຫນ້າທໍາອິດ, ພວກເຮົາຄູນ 10 ແລະ 20 ໃຫ້ໄດ້ 200 ຫຼັງຈາກນັ້ນເອົາກັບຄືນ (10 + 20)% 100 = 30. ດຽວນີ້ພວກເຮົາມີ [30, 30]. ແລ້ວຄູນ 30 * 30 = 900. ດັ່ງນັ້ນ ຄຳ ຕອບແມ່ນ 900 + 200 = 1100.

ຖ້າພວກເຮົາຈະໄດ້ຄູນ 20 ແລະ 30 ກ່ອນ. ພວກເຮົາຈະໄດ້ (20 * 30) + (10 * 50) = 1100. ດັ່ງນັ້ນທັງສອງທາງພວກເຮົາຈະໄດ້ຜົນດຽວກັນ.

ວິທີການ

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

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

ລະຫັດ

ລະຫັດ C ++ ເພື່ອຊອກຫາຜົນບວກຕ່ ຳ ສຸດຂອງຄູນເລກເລກ n

#include <bits/stdc++.h>
using namespace std;
int dp[5][5];
int sum(int i, int j, int a[]){
  int ans = 0;
  for (int k=i;k<=j;k++)
    ans=(ans+a[k])%100;
  return ans;
}

int minimumSum(int i, int j, int a[]){
    if(i==j)return 0;
  if (dp[i][j] != INT_MAX)
    return dp[i][j];
    // divide the problem into subproblems
  for(int k=i;k<j;k++)
        dp[i][j] = min(dp[i][j], minimumSum(i,k,a)+minimumSum(k+1,j,a) + sum(i,k,a)*sum(k+1,j,a));
  return dp[i][j];
}

int main() {
  int a[] = {10, 20, 30};
  int n = sizeof(a) / sizeof(a[0]);
  for(int i=0;i<5;i++){
        for(int j=0;j<5;j++)
            dp[i][j] = INT_MAX;
  }
  cout<<minimumSum(0,n-1,a);
}
1100

ລະຫັດ Java ເພື່ອຊອກຫາຜົນບວກຕ່ ຳ ສຸດຂອງຄູນເລກເລກ n

import java.util.*;
class Main{
  static int dp[][] = new int[5][5];
  static int sum(int i, int j, int a[]){
    int ans = 0;
    for (int k=i;k<=j;k++)
      ans=(ans+a[k])%100;
    return ans;
  }

  static int minimumSum(int i, int j, int a[]){
      if(i==j)return 0;
    if (dp[i][j] != Integer.MAX_VALUE)
      return dp[i][j];
      // divide the problem into subproblems
    for(int k=i;k<j;k++)
          dp[i][j] = Math.min(dp[i][j], minimumSum(i,k,a)+minimumSum(k+1,j,a) + sum(i,k,a)*sum(k+1,j,a));
    return dp[i][j];
  }

  public static void main(String[] args)
  {
    int a[] = {10, 20, 30};
    int n = a.length;
    for(int i=0;i<5;i++){
          for(int j=0;j<5;j++)
              dp[i][j] = Integer.MAX_VALUE;
    }
    int ans = minimumSum(0,n-1,a);
    	System.out.print(ans);
  	}
}
1100

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

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

O (N ^ 3), ເນື່ອງຈາກວ່າມີ N ^ 2 ລັດແລະເພື່ອ ຄຳ ນວນຜົນ ສຳ ລັບແຕ່ລະຄົນພວກເຮົາແມ່ນຂື້ນກັບ ຈຳ ນວນລັດ N ປະມານ. ດັ່ງນັ້ນຄວາມສັບສົນທີ່ໃຊ້ເວລາແມ່ນ polynomial.

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

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