จำนวนเลขไม่เกิน N จากชุดตัวเลขใน C++

คำอธิบายปัญหา

ให้ชุดตัวเลข D (subset ของ {1..9} เรียงแล้ว) เขียนเลขได้โดยใช้ตัวเลขใน D ซ้ำได้ หาจำนวนเลขบวก ≤ N

ตัวอย่าง

D = [2,3,4,7], N = 100 → Output: 20

แนวทางแก้ปัญหา: Digit DP แบบ Greedy

1. นับเลขที่มีหลักน้อยกว่า N: Σ |D|ⁱ สำหรับ i=1..len(N)-1
2. นับเลขที่มีหลักเท่ากัน N (most significant digit first):
   • สำหรับแต่ละตำแหน่ง i นับตัวเลขใน D ที่ < N[i] → เพิ่ม |D|^(remaining)
   • ถ้ามีตัวเลขใน D == N[i] → ดำเนินต่อตำแหน่งถัดไป
   • ถ้าไม่มี → หยุด
3. ถ้าเดินครบทุกตำแหน่ง → เพิ่ม 1 (N เอง)

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

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

class Solution {
public:
    int atMostNGivenDigitSet(vector<string>& D, int N) {
        string n = to_string(N);
        int sz = n.size(), ret = 0;
        
        // นับเลขหลักน้อยกว่า
        for(int i=1; i