动态规划常用算法,动态规划lcs

AcWing 338. 计数问题   思路分析 代码展示 

#include <iostream>#include <algorithm>#include <cstring>#include <vector>using namespace std;//10的x次方int pow10(int x){    int res  1;    while(x --) res * 10;    return res;}int get(vector<int> num, int l, int r){    int res  0;        for (int i  l; i > r; i --)        res  res * 10  num[i];    return res;}int count(int n, int x){    //当n  0时    if (!n) return 0;        vector<int> num;    //把每一位数存到数组中去    while (n)    {        num.push_back(n % 10);        n / 10;    }        n  num.size();    int res  0;    //枚举每一位    //当x为0时,因为0不会出现在最高位高位不用枚举,所以直接从第二位开始枚举    for (int i  n - 1 - !x; i > 0; i --)    {        //第一种情况    当只有一位数时,不可能出现第一种情况        if (i < n - 1)        {            res  get(num, n - 1, i  1) * pow10(i);            //当x  0时,x左边的位数需要从1开始枚举,但是第一种情况是从0开始枚举,所以需要处理一下细节            if (x  0) res - pow10(i);        }        //第二种情况            if (x < num[i]) res  pow10(i);        else if (x  num[i]) res  get(num, i - 1, 0)  1;    }    return res;}int main(){    while (true)    {        int a, b;        cin >> a >> b;        if (a  0 && b  0) break;                if (a > b) swap(a, b);                for (int i  0; i < 10; i )            cout << count(b, i) - count(a - 1, i) <<  ;                    cout << endl;    }        return 0;}