Berbagi teknologi

Perpustakaan Sumber Daya Touge (24) Sisipkan tanda tambah

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. Deskripsi masalah

2. Pemikiran Algoritma  

Pemrograman dinamis dapat digunakan untuk mengatasi masalah ini.

Pertama, pisahkan string angka menjadi beberapa angka, dan gunakan array angka untuk menyimpan setiap angka. Misalnya, string angka 79846 akan dipecah menjadi array [7, 9, 8, 4, 6].

Kemudian tentukan array dua dimensi dp, dimana dp[i][j] mewakili nilai minimum yang dapat diperoleh dengan menyisipkan tanda j plus ke dalam i bilangan pertama. Inisialisasi array dp hingga tak terhingga, kecuali dp[0][0] = 0.

Kemudian gunakan dua loop untuk memperbarui array dp. Perulangan bagian luar melintasi setiap angka dalam rangkaian angka, dan putaran dalam melintasi jumlah tanda tambah yang disisipkan. Untuk setiap dp[i][j], Anda dapat mempertimbangkan untuk menggabungkan angka nums[i] dengan angka sebelumnya untuk membentuk angka baru, atau menyisipkan tanda plus di antara angka nums[i] dan angka sebelumnya. Ambil nilai yang lebih kecil dari kedua kasus tersebut sebagai nilai dp[i][j].

Terakhir, nilai minimum pada baris terakhir array dp adalah nilai minimum yang dicari.

3. Implementasi kode  

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <limits.h>
  4. #include <stdlib.h>
  5. // Helper function to extract integer value from substring
  6. int getNumber(char* str, int start, int end) {
  7. char buffer[12]; // Buffer large enough for max 10 digits + '0'
  8. int length = end - start + 1;
  9. strncpy(buffer, str + start, length);
  10. buffer[length] = '0';
  11. return atoi(buffer);
  12. }
  13. int main() {
  14. char str[201];
  15. int M;
  16. scanf("%s %d", str, &M);
  17. int n = strlen(str);
  18. int dp[n+1][M+1];
  19. // Initialize dp array with large numbers
  20. for (int i = 0; i <= n; i++) {
  21. for (int j = 0; j <= M; j++) {
  22. dp[i][j] = INT_MAX;
  23. }
  24. }
  25. // Base case: no splits
  26. dp[0][0] = 0;
  27. // Dynamic programming to calculate minimum sum
  28. for (int i = 1; i <= n; i++) {
  29. for (int j = 0; j <= M; j++) { // j can be 0 as well
  30. if (j == 0) {
  31. dp[i][j] = getNumber(str, 0, i-1);
  32. } else {
  33. for (int k = 1; k < i; k++) { // k starts from 1
  34. if (dp[k][j-1] != INT_MAX) {
  35. int num = getNumber(str, k, i-1);
  36. if (dp[k][j-1] + num < dp[i][j]) {
  37. dp[i][j] = dp[k][j-1] + num;
  38. }
  39. }
  40. }
  41. }
  42. }
  43. }
  44. // Find the minimum value in dp[n][*] with M splits
  45. int result = INT_MAX;
  46. for (int i = 0; i <= M; i++) {
  47. if (dp[n][i] < result) {
  48. result = dp[n][i];
  49. }
  50. }
  51. printf("%dn", result);
  52. return 0;
  53. }

Hasil dari

 Kesimpulan       

keinginan untuk meningkatkan semangat

Ketekunan mampu menghaluskan gunung

!!!