จำนวนการดำเนินการน้อยที่สุดเพื่อสร้างสตริงไบนารี S ด้วย C++

ข้อความโจทย์

กำหนดสตริงไบนารี str ให้หาจำนวนการดำเนินการขั้นต่ำที่ต้องทำเพื่อสร้างตัวเลขที่แทนโดย str มีเพียงการดำเนินการต่อไปนี้เท่านั้น -

• บวก 2^x
• ลบ 2^x

ถ้าสตริงไบนารีคือ "1000" เราต้องทำเพียง 1 การดำเนินการ คือ บวก 2³

ถ้าสตริงไบนารีคือ "101" เราต้องทำ 2 การดำเนินการ คือ บวก 2² + 2⁰

ตัวอย่างโค้ด

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int getMinOperations(string s) {
    reverse(s.begin(), s.end());
    int n = s.length();
    int result[n + 1][2];

    if (s[0] == '0') {
        result[0][0] = 0;
    } else {
        result[0][0] = 1;
    }
    result[0][1] = 1;

    for (int i = 1; i < n; ++i) {
        if (s[i] == '0') {
            result[i][0] = result[i - 1][0];
            result[i][1] = 1 + min(result[i - 1][1], result[i - 1][0]);
        } else {
            result[i][1] = result[i - 1][1];
            result[i][0] = 1 + min(result[i - 1][0], result[i - 1][1]);
        }
    }
    return result[n - 1][0];
}

int main() {
    string str = "101";
    cout << "Minimum required operations = " << getMinOperations(str) << endl;
    return 0;
}

ผลลัพธ์

เมื่อคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้ -

Minimum required operations = 2