• 动态规划（AcWing）： 1）计数类DP，2）树形DP，3）记忆化搜索，4）状态压缩DP，5）数位统计DP；

    1）计数类DP：

    900. 整数划分

    一个正整数 n

    可以表示成若干个正整数之和，形如：n=n1+n2+…+nk，其中 n1≥n2≥…≥nk,k≥1

    。

    我们将这样的一种表示称为正整数 n

    的一种划分。

    现在给定一个正整数 n

    ，请你求出 n

    共有多少种不同的划分方法。

    输入格式

    共一行，包含一个整数 n

    。

    输出格式

    共一行，包含一个整数，表示总划分数量。

    由于答案可能很大，输出结果请对 109+7

    取模。

    数据范围

    1≤n≤1000

    输入样例:

    5

    输出样例：

    7

      * 可以将此题理解为完全背包问题来解救；
     * 状态表示：dp[i][j] ： 表示只选择前i个数，和为j的组合方案有多少；
     *
     * 因为 dp[i][j] = dp[i-1][j] + dp[i-1][j-i] +
     * dp[i-1][j-i*2] +……+ )
     *
     * 又因为 dp[i][j-i] = dp[i-1][j-i] + dp[i-1][j-2*i] +
     * dp[i-1][j-3*i] + …… + ；
     * 所以 dp[i][j] = dp[i-1][j],dp[i][j-i] ;
     *
     * 观摩动态转移方程，我们会发现：
     * dp[i-1][j] , dp[i][j-i] 一定先于 dp[i][j] 计算出来，因此我们就可以
     * 完整的，正确的得到这个解，但是在此之前，我们也得看一下第一个数该初始化
     * 哪些数据才能使之正确；
     * 第一个数据是 dp[1][0] , 那么想必初始化dp[0][0] = 1 即可；意味着我选择
     * 前0个数的和是0，我选择0个数有0种选择，我一个数都不选择有一种方案，
     * 所以 dp[0][0] = 1即是正确的；（但是这种只初始化一个数据时，需要j从0开始
     * 枚举；）
     * 我们可以把选择前k个数，和为0的方案的值全部初始化为1，由上分析，这显然是
     * 正确的；
     *
     * 从评论区学到一种初始化的方法，当初始化的值由题目的定义不好得出直接答案时，
     * 从当前的状态转移方程和题目定义的第一个状态的值 去倒推初始化数据的值，
     * 而使得这个初始化的值能够保证状态转移方程是正确的。

    1. /**
    2.  * 可以将此题理解为完全背包问题来解救；
    3.  * 状态表示：dp[i][j] ： 表示只选择前i个数，和为j的组合方案有多少；
    4.  * 
    5.  * 因为 dp[i][j] = dp[i-1][j] + dp[i-1][j-i] + 
    6.  * dp[i-1][j-i*2] +……+ )
    7.  * 
    8.  * 又因为 dp[i][j-i] = dp[i-1][j-i] + dp[i-1][j-2*i] + 
    9.  * dp[i-1][j-3*i] + …… + ；
    10.  * 所以 dp[i][j] = dp[i-1][j],dp[i][j-i] ;
    11.  * 
    12.  * 观摩动态转移方程，我们会发现：
    13.  * dp[i-1][j] , dp[i][j-i] 一定先于 dp[i][j] 计算出来，因此我们就可以
    14.  * 完整的，正确的得到这个解，但是在此之前，我们也得看一下第一个数该初始化
    15.  * 哪些数据才能使之正确；
    16.  * 第一个数据是 dp[1][0] , 那么想必初始化dp[0][0] = 1 即可；意味着我选择
    17.  * 前0个数的和是0，我选择0个数有0种选择，我一个数都不选择有一种方案，
    18.  * 所以 dp[0][0] = 1即是正确的；（但是这种只初始化一个数据时，需要j从0开始
    19.  * 枚举；）
    20.  * 我们可以把选择前k个数，和为0的方案的值全部初始化为1，由上分析，这显然是
    21.  * 正确的；
    22.  * 
    23.  * 从评论区学到一种初始化的方法，当初始化的值由题目的定义不好得出直接答案时，
    24.  * 从当前的状态转移方程和题目定义的第一个状态的值 去倒推初始化数据的值，
    25.  * 而使得这个初始化的值能够保证状态转移方程是正确的。
    26. */
    27.  
    28. #include <iostream>
    29. #include <algorithm>
    30.  
    31. using namespace std;
    32.  
    33. const int maxn = 1010 , mod = 1e9+7;
    34. int dp[maxn][maxn];
    35.  
    36. int main()
    37. {
    38.     int n;
    39.     cin >> n;
    40.     
    41.     dp[0][0]=1;
    42.     
    43.     for(int i=1;i<=n;++i)
    44.         for(int j=0;j<=n;++j)
    45.         {
    46.             if(j<i)
    47.                 dp[i][j] = dp[i-1][j];
    48.             else
    49.                 dp[i][j] = (dp[i-1][j] + dp[i][j-i])%mod;
    50.         }
    51.         
    52.     cout << dp[n][n] << endl;
    53.     return 0;
    54. }
    55.  
    56.

    //滚动数组优化

    1. //滚动数组优化
    2.  
    3. #include <iostream>
    4. #include <algorithm>
    5.  
    6. using namespace std;
    7.  
    8. const int maxn = 1010 , mod = 1e9+7;
    9. int dp[maxn];
    10.  
    11. int main()
    12. {
    13.     int n;
    14.     cin >> n;
    15.     
    16.     dp[0]=1;
    17.     
    18.     for(int i=1;i<=n;++i)
    19.         for(int j=0;j<=n;++j)
    20.         {
    21.             if(j<i)
    22.                 dp[j] = dp[j];
    23.             else
    24.                 dp[j] = (dp[j] + dp[j-i])%mod;
    25.         }
    26.         
    27.     cout << dp[n] << endl;
    28.     return 0;
    29. }

     * dp[i][j] 表示选择了i个数，和为j的方案总数；
     * 状态转移方程：dp[i][j] = dp[i-1][j-1] + dp[i][j-i] ;
     * (最小值等于1的数的方案，或者最小值大于1的数的方案)；
     * 1）把最小值1去掉,选择的数目个数为i-1，和为j-1，dp[i][j] = dp[i-1][j-1]；
     * 2）把每个值都减去一，由于最小值是大于1的，所以减去之后最小值最小也是1，
     *    所以 dp[i][j] = dp[i][j-i]；
     * 把 1）和2）的结果加起来即为 dp[i][j]的值；

    1. /**
    2.  * dp[i][j] 表示选择了i个数，和为j的方案总数；
    3.  * 状态转移方程：dp[i][j] = dp[i-1][j-1] + dp[i][j-i] ;
    4.  * (最小值等于1的数的方案，或者最小值大于1的数的方案)；
    5.  * 1）把最小值1去掉,选择的数目个数为i-1，和为j-1，dp[i][j] = dp[i-1][j-1]；
    6.  * 2）把每个值都减去一，由于最小值是大于1的，所以减去之后最小值最小也是1，
    7.  *    所以 dp[i][j] = dp[i][j-i]；
    8.  * 把 1）和2）的结果加起来即为 dp[i][j]的值；
    9. */
    10.  
    11. #include <iostream>
    12. #include <algorithm>
    13.  
    14. using namespace std;
    15.  
    16. const int maxn = 1010 , mod = 1e9+7;
    17. int dp[maxn][maxn];
    18.  
    19. int main()
    20. {
    21.     int n;
    22.     cin >> n;
    23.     
    24.     for(int i=0;i<=n;++i)
    25.         dp[1][i] = 1;   //选择1个数，和为i的方案必定只有一种
    26.         
    27.     for(int i=1;i<=n;++i)
    28.         for(int j=i;j<=n;++j)
    29.         {
    30.             if(j == i)  //if语句不需要也行，因为这句已经已经包含在else语句中了
    31.                 dp[i][j] = 1 ;  //选择i个数，和为i的方案也必定只有一种
    32.             else
    33.                 dp[i][j] = (dp[i-1][j-1] + dp[i][j-i])%mod;
    34.         }
    35.         
    36.     int res = 0;    //需要累加一下
    37.     for(int i=1;i<=n;++i)
    38.         res = (res+dp[i][n]) % mod;
    39.         
    40.     cout << res << endl;
    41.     return 0;
    42. }

    2）树形DP：

    285. 没有上司的舞会

    Ural 大学有 N

    名职员，编号为 1∼N

    。

    他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。

    每个职员有一个快乐指数，用整数 Hi

    给出，其中 1≤i≤N

    。

    现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。

    在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

    输入格式

    第一行一个整数 N

    。

    接下来 N

    行，第 i 行表示 i 号职员的快乐指数 Hi

    。

    接下来 N−1

    行，每行输入一对整数 L,K，表示 K 是 L

    的直接上司。

    输出格式

    输出最大的快乐指数。

    数据范围

    1≤N≤6000

    ,
    −128≤Hi≤127

    输入样例：

    1. 7
    2. 1
    3. 1
    4. 1
    5. 1
    6. 1
    7. 1
    8. 1
    9. 1 3
    10. 2 3
    11. 6 4
    12. 7 4
    13. 4 5
    14. 3 5

    输出样例：

    5

      * 树形 dp，每个节点有选与不选两种方案，所以我们可以用dp[maxn][2]用来做
     * 状态表示：
     * dp[u][0]:以u为根节点的子树的最大快乐指数,并且不能选择u；
     * dp[u][1]:以u为根节点的子树的最大快乐指数，并且可以选择u；
     *
     * 不选择u这个节点，那么我们就可以既选择u的孩子节点，也可以不选择u的孩子
     * 节点；
     * 选择u这个结点，那么我们肯定是不能选择u的孩子节点的。
     *
     * 状态计算：
     * dp[u][0] = dp[u][0] + max(dp[v][1],dp[v][0]);
     * dp[u][1] = max( dp[u][1] , (dp[u][1] + dp[v][0]) );
     *  但只要我们能保证dp[v][0]非负，我们就可以将 dp[u][1]简化为：
     *  dp[u][1] = dp[u][1]+dp[v][0];
     *  由dp的定义，我们一定能确定dp[v][0]非负，最糟糕的情况莫过于所有节点
     *  的快乐值都为负数，我所有节点都不选，那么dp[v][0]=0;
     *
     * dp[u][0] = dp[u][0] + max(dp[v][1],dp[v][0]);
     * 你说为什么要把dp[u][0]的值也要累加给dp[u][0],即为什么不能是:
     * dp[u][0] = max(dp[v][1],dp[v][0]);
     * 这是因为u有可能由多个孩子节点，根据题意，如果以孩子节点为根的子树的
     * 最大快乐值都是正数，那么肯定得把所有子树都加上，即在孩子节点v之前已经
     * 有孩子结点j的值加到dp[u][0] 上了，那在考虑孩子节点v的时候，是肯定得加上
     * dp[u][0] 的值。
     * 同理，dp[u][1]一样。

    1. /**
    2.  * 树形 dp，每个节点有选与不选两种方案，所以我们可以用dp[maxn][2]用来做
    3.  * 状态表示：
    4.  * dp[u][0]:以u为根节点的子树的最大快乐指数,并且不能选择u；
    5.  * dp[u][1]:以u为根节点的子树的最大快乐指数，并且可以选择u；
    6.  * 
    7.  * 不选择u这个节点，那么我们就可以既选择u的孩子节点，也可以不选择u的孩子
    8.  * 节点；
    9.  * 选择u这个结点，那么我们肯定是不能选择u的孩子节点的。
    10.  * 
    11.  * 状态计算：
    12.  * dp[u][0] = dp[u][0] + max(dp[v][1],dp[v][0]);
    13.  * dp[u][1] = max( dp[u][1] , (dp[u][1] + dp[v][0]) );
    14.  *  但只要我们能保证dp[v][0]非负，我们就可以将 dp[u][1]简化为：
    15.  *  dp[u][1] = dp[u][1]+dp[v][0];
    16.  *  由dp的定义，我们一定能确定dp[v][0]非负，最糟糕的情况莫过于所有节点
    17.  *  的快乐值都为负数，我所有节点都不选，那么dp[v][0]=0;
    18.  * 
    19.  * dp[u][0] = dp[u][0] + max(dp[v][1],dp[v][0]);
    20.  * 你说为什么要把dp[u][0]的值也要累加给dp[u][0],即为什么不能是:
    21.  * dp[u][0] = max(dp[v][1],dp[v][0]);
    22.  * 这是因为u有可能由多个孩子节点，根据题意，如果以孩子节点为根的子树的
    23.  * 最大快乐值都是正数，那么肯定得把所有子树都加上，即在孩子节点v之前已经
    24.  * 有孩子结点j的值加到dp[u][0] 上了，那在考虑孩子节点v的时候，是肯定得加上
    25.  * dp[u][0] 的值。
    26.  * 同理，dp[u][1]一样。
    27.  * 
    28. */
    29.  
    30. #include <iostream>
    31. #include <algorithm>
    32.  
    33. using namespace std;
    34.  
    35. const int maxn = 6010;
    36. vector<int> Adj[maxn];
    37. bool hs[maxn];  //确定根节点
    38. int c[maxn];    //结点的快乐值
    39. int dp[maxn][2];    //状态表示
    40.  
    41. void dfs(int u)
    42. {
    43.     dp[u][1] = c[u]; //起初，以u为根的子树只有u这一个结点
    44.     
    45.     
    46.     for(int i=0;i<Adj[u].size();++i)
    47.     {
    48.         int v = Adj[u][i];
    49.         dfs(v);
    50.         
    51.         dp[u][0] = max(dp[v][0] , dp[v][1]);
    52.         //dp[u][1] += dp[v][0]; //这个和下面一个都可
    53.         dp[u][1] = max(dp[u][1] , dp[u][1]+dp[v][0]);
    54.     }
    55. }
    56.  
    57. int main()
    58. {
    59.     int n;
    60.     cin >> n;
    61.     
    62.     for(int i=1;i<=n;++i)
    63.         cin >> c[i];
    64.         
    65.     for(int i=1;i<n;++i)
    66.     {
    67.         int u,v;
    68.         cin >> v >> u;
    69.         Adj[u].push_back(v);    
    70.         hs[v] = 1;
    71.     }
    72.     
    73.     int root = 1;
    74.     while(hs[root])
    75.         ++root;
    76.         
    77.     dfs(root);
    78.     
    79.     cout << max(dp[root][0] , dp[root][1]) << endl;
    80.     
    81.         
    82.     return 0;
    83. }

    3）记忆化搜索：

    901. 滑雪

    给定一个 R

    行 C

    列的矩阵，表示一个矩形网格滑雪场。

    矩阵中第 i

    行第 j 列的点表示滑雪场的第 i 行第 j

    列区域的高度。

    一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。

    当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。

    下面给出一个矩阵作为例子：

    1.  1  2  3  4 5
    2.  
    3. 16 17 18 19 6
    4.  
    5. 15 24 25 20 7
    6.  
    7. 14 23 22 21 8
    8.  
    9. 13 12 11 10 9

    在给定矩阵中，一条可行的滑行轨迹为 24−17−2−1

    。

    在给定矩阵中，最长的滑行轨迹为 25−24−23−…−3−2−1

    ，沿途共经过 25

    个区域。

    现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。

    输入格式

    第一行包含两个整数 R

    和 C

    。

    接下来 R

    行，每行包含 C

    个整数，表示完整的二维矩阵。

    输出格式

    输出一个整数，表示可完成的最长滑雪长度。

    数据范围

    1≤R,C≤300

    ,
    0≤矩阵中整数≤10000

    输入样例：

    1. 5 5
    2. 1 2 3 4 5
    3. 16 17 18 19 6
    4. 15 24 25 20 7
    5. 14 23 22 21 8
    6. 13 12 11 10 9

    输出样例：

    25

     * 状态表示：dp[i][j] : 从(i,j)这个点开始滑离，能滑的最远距离；
     * 状态计算：
     *  从上来：dp[i,j] = max(dp[i,j] , dp[i-1,j]+1);
     *  从下来：dp[i,j] = max(dp[i,j] , dp[i+1,j]+1);
     *  从左来：dp[i,j] = max(dp[i,j] , dp[i,j-1]+1);
     *  从右来：dp[i,j] = max(dp[i,j] , dp[i,j+1]+1);

    1. /**
    2.  * 状态表示：dp[i][j] : 从(i,j)这个点开始滑离，能滑的最远距离；
    3.  * 状态计算：
    4.  *  从上来：dp[i,j] = max(dp[i,j] , dp[i-1,j]+1);
    5.  *  从下来：dp[i,j] = max(dp[i,j] , dp[i+1,j]+1);
    6.  *  从左来：dp[i,j] = max(dp[i,j] , dp[i,j-1]+1);
    7.  *  从右来：dp[i,j] = max(dp[i,j] , dp[i,j+1]+1);
    8. */
    9.  
    10. #include <iostream>
    11. #include <algorithm>
    12.  
    13. using namespace std;
    14.  
    15. const int maxn = 310;
    16. int g[maxn][maxn];  //地图
    17. int dp[maxn][maxn]; //状态表示
    18. int n,m;
    19.  
    20. int dx[]={0,1,0,-1}; //坐标偏移量
    21. int dy[]={1,0,-1,0};
    22.  
    23. int dfs(int x,int y)    
    24. {
    25.     int &v = dp[x][y];
    26.     if(v!=0)    return v;   //如果dp[x][y]已经计算过，直接返回其值；
    27.     
    28.     v=1;
    29.     for(int i=0;i<4;++i)
    30.     {
    31.         int a = x+dx[i],b = y+dy[i];
    32.         if(a>=1 && a<=n && b>=1 && b<=m && g[a][b] < g[x][y])
    33.             v = max(v,dfs(a,b)+1);   //如果从(a,b) 到(x,y)能使dp[x][y]变大 
    34.     }
    35.     return v;
    36. }
    37.  
    38. int main()
    39. {
    40.     cin >> n >> m;
    41.     
    42.     for(int i=1;i<=n;++i)
    43.         for(int j=1;j<=m;++j)
    44.             cin >> g[i][j];
    45.         
    46.     int res = 0;
    47.     for(int i=1;i<=n;++i)
    48.         for(int j=1;j<=m;++j)
    49.             res = max(res,dfs(i,j));
    50.         
    51.     cout << res << endl;
    52.     return 0;
    53. }

    4）状态压缩DP：

    91. 最短Hamilton路径

    给定一张 n

    个点的带权无向图，点从 0∼n−1 标号，求起点 0 到终点 n−1

    的最短 Hamilton 路径。

    Hamilton 路径的定义是从 0

    到 n−1

    不重不漏地经过每个点恰好一次。

    输入格式

    第一行输入整数 n

    。

    接下来 n

    行每行 n 个整数，其中第 i 行第 j 个整数表示点 i 到 j 的距离（记为 a[i,j]

    ）。

    对于任意的 x,y,z

    ，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]≥a[x,z]

    。

    输出格式

    输出一个整数，表示最短 Hamilton 路径的长度。

    数据范围

    1≤n≤20


    0≤a[i,j]≤107

    输入样例：

    1. 5
    2. 0 2 4 5 1
    3. 2 0 6 5 3
    4. 4 6 0 8 3
    5. 5 5 8 0 5
    6. 1 3 3 5 0

    输出样例：

    18

      * 状态压缩dp：将某一维的值用二进制数来表示，将用二进制表示的值看作是若干
     * 种状态，每一位上的值表示一种状态，可根据具体题目来设定，例如，可以将每
     * 一位上二进制值为1表示某个点已经在这个集合中，反之，值为0表示这个点没有
     * 在集合中。
     *
     * 对于这个题目：
     * 状态设计：dp[i][j]:从起点到j，中间途径i用二进制表示的位为1的点的路径距离
     * 最小值；
     *
     * 状态转移方程：
     *  1）中途不途径k：dp[i][j] = dp[i][j];
     *  2）中途从k转移过来：
     *      dp[i][j] = min(dp[i][j],dp[i - (1<  *      选不选择从k到j，还是得比较一下的;
     *
     * 初始化:dp[1][0] = 0;从起点到起点不需要距离；
     * 答案：dp[(1<  *       j等于n-1；

    1. /**
    2.  * 状态压缩dp：将某一维的值用二进制数来表示，将用二进制表示的值看作是若干
    3.  * 种状态，每一位上的值表示一种状态，可根据具体题目来设定，例如，可以将每
    4.  * 一位上二进制值为1表示某个点已经在这个集合中，反之，值为0表示这个点没有
    5.  * 在集合中。
    6.  * 
    7.  * 对于这个题目：
    8.  * 状态设计：dp[i][j]:从起点到j，中间途径i用二进制表示的位为1的点的路径距离
    9.  * 最小值；
    10.  * 
    11.  * 状态转移方程：
    12.  *  1）中途不途径k：dp[i][j] = dp[i][j];
    13.  *  2）中途从k转移过来：
    14.  *      dp[i][j] = min(dp[i][j],dp[i - (1<
    15.  *      选不选择从k到j，还是得比较一下的;
    16.  * 
    17.  * 初始化:dp[1][0] = 0;从起点到起点不需要距离；
    18.  * 答案：dp[(1<
    19.  *       j等于n-1；
    20. */
    21.  
    22. #include <iostream>
    23. #include <algorithm>
    24.  
    25. using namespace std;
    26.  
    27. const int N = 20,M=1<<N;
    28. int w[N][N];    //距离
    29. int dp[M][N];   //状态表示
    30.  
    31. int main()
    32. {
    33.     int n;
    34.     cin >> n;
    35.     
    36.     for(int i=0;i<n;++i)
    37.         for(int j=0;j<n;++j)
    38.             cin >> w[i][j];
    39.     
    40.     fill(*dp,*dp+N*M,M);
    41.     dp[1][0]=0;  //初始化，从起点到起点不需要距离；
    42.     
    43.     for(int i=1;i < 1<<n ; ++i) //枚举一个点，两个点,...,n个点
    44.         for(int j=0;j<n;++j)    //这种路径所走过的点j
    45.             if(i>>j & 1)
    46.             {
    47.                 for(int k=0;k<n;++k)//这种路径是否能从k到j使得起点到j的距离变小
    48.                     if(i>>k & 1)
    49.                         dp[i][j] = min(dp[i][j],dp[i - (1<<j)][k]+w[k][j]);
    50.             }
    51.             
    52.     //i用二进制表示从低到高位有连续的n个1，j等于n-1；
    53.     cout << dp[(1<<n) -1][n-1] << endl;
    54.     return 0;
    55. }

    5）数位统计DP：

    338. 计数问题

    给定两个整数 a

    和 b，求 a 和 b 之间的所有数字中 0∼9

    的出现次数。

    例如，a=1024，b=1032

    ，则 a 和 b 之间共有 9

    个数如下：

    1024 1025 1026 1027 1028 1029 1030 1031 1032

    其中 0 出现 10

    次，1 出现 10 次，2 出现 7 次，3 出现 3

    次等等…

    输入格式

    输入包含多组测试数据。

    每组测试数据占一行，包含两个整数 a

    和 b

    。

    当读入一行为 0 0 时，表示输入终止，且该行不作处理。

    输出格式

    每组数据输出一个结果，每个结果占一行。

    每个结果包含十个用空格隔开的数字，第一个数字表示 0 出现的次数，第二个数字表示 1 出现的次数，以此类推。

    数据范围

    0

    输入样例：

    1. 1 10
    2. 44 497
    3. 346 542
    4. 1199 1748
    5. 1496 1403
    6. 1004 503
    7. 1714 190
    8. 1317 854
    9. 1976 494
    10. 1001 1960
    11. 0 0

    输出样例：

    1. 1 2 1 1 1 1 1 1 1 1
    2. 85 185 185 185 190 96 96 96 95 93
    3. 40 40 40 93 136 82 40 40 40 40
    4. 115 666 215 215 214 205 205 154 105 106
    5. 16 113 19 20 114 20 20 19 19 16
    6. 107 105 100 101 101 197 200 200 200 200
    7. 413 1133 503 503 503 502 502 417 402 412
    8. 196 512 186 104 87 93 97 97 142 196
    9. 398 1375 398 398 405 499 499 495 488 471
    10. 294 1256 296 296 296 296 287 286 286 247

     * 考虑 1——abcdefg 中有多少个x：
     * 我们先假设第三位固定是x，此时所有情况中x的个数有多少个？
     *  1）【1】先假定 x!=0 ，则ab可取00 ~ ab-1，对于每一个ab的组合，defg都可取：
     *     0000 ~ 9999 共1e4种组合；
     *     【2】如果x == 0，那么x之前的数就不能取0了，因为数字不能存在前导0的
     *      情况，所以ab可取01 ~ ab-1，对于每一个ab的组合，defg都可取：
     *      0000 ~ 9999 共1e4种组合；
     *  2）如果取前两位等于ab，那么c就要分情况讨论：
     *      【1】如果 c>x ,那么defg 可取：0000 ~ 9999 共1e4种组合；
     *      【2】如果 c == x，那么defg 可取：0000 ~ defg 共 defg+1 种组合；
     *      【3】如果 c < x，那么defg 不可取任何数，此时在1~abcdefg内找不出
     *          一个符合条件的数。

    1. /**
    2.  * 考虑 1——abcdefg 中有多少个x：
    3.  * 我们先假设第三位固定是x，此时所有情况中x的个数有多少个？
    4.  *  1）【1】先假定 x!=0 ，则ab可取00 ~ ab-1，对于每一个ab的组合，defg都可取：
    5.  *     0000 ~ 9999 共1e4种组合；
    6.  *     【2】如果x == 0，那么x之前的数就不能取0了，因为数字不能存在前导0的
    7.  *      情况，所以ab可取01 ~ ab-1，对于每一个ab的组合，defg都可取：
    8.  *      0000 ~ 9999 共1e4种组合；
    9.  *  2）如果取前两位等于ab，那么c就要分情况讨论：
    10.  *      【1】如果 c>x ,那么defg 可取：0000 ~ 9999 共1e4种组合；
    11.  *      【2】如果 c == x，那么defg 可取：0000 ~ defg 共 defg+1 种组合；
    12.  *      【3】如果 c < x，那么defg 不可取任何数，此时在1~abcdefg内找不出
    13.  *          一个符合条件的数。
    14. */
    15.  
    16. #include <iostream>
    17. #include <algorithm>
    18. #include <cmath>
    19.  
    20. using namespace std;
    21.  
    22. int count(int n,int x)  //计算1~n中有多少个x
    23. {
    24.     int cnt = 0,m = n;
    25.     int res = 0; //res计算结果
    26.     while (m) //cnt存储n的位数
    27.     {
    28.         ++cnt; 
    29.         m/=10;
    30.     }
    31.     
    32.     for(int i=0;i<cnt;++i)  
    33.     {
    34.         int r = pow(10,i); //第i位右边最多可能存在的不同组合数是多少
    35.         int l = n/r/10;    //第i位左边的数字是多少
    36.         
    37.         if(x)    //如果第i位不是0
    38.             res += r*l;
    39.         else
    40.             res += (l-1)*r;
    41.           
    42.         if( n/r % 10 > x) //如果第i位的数字比x大
    43.             res += r;
    44.         else if( n/r % 10 == x) //如果第i位的数字和x一样大
    45.             res += (n%r+1);
    46.     }
    47.     return res;
    48. }
    49.  
    50. int main()
    51. {
    52.     int a,b;
    53.     while(cin >> a >> b,a || b)
    54.     {
    55.         if(a < b)
    56.             swap(a,b);
    57.         
    58.         for(int i=0;i<=9;++i)
    59.             cout << count(a,i) - count(b-1,i) << ' '; 
    60.             //与前缀和的思想是一样的；
    61.         puts("");
    62.     }
    63.     
    64.     return 0;
    65. }

     

    4)这也属于状态压缩dp

    291. 蒙德里安的梦想

    求把 N×M

    的棋盘分割成若干个 1×2

    的长方形，有多少种方案。

    例如当 N=2，M=4

    时，共有 5 种方案。当 N=2，M=3 时，共有 3

    种方案。

    如下图所示：

    输入格式

    输入包含多组测试用例。

    每组测试用例占一行，包含两个整数 N

    和 M

    。

    当输入用例 N=0，M=0

    时，表示输入终止，且该用例无需处理。

    输出格式

    每个测试用例输出一个结果，每个结果占一行。

    数据范围

    1≤N,M≤11

    输入样例：

    1. 1 2
    2. 1 3
    3. 1 4
    4. 2 2
    5. 2 3
    6. 2 4
    7. 2 11
    8. 4 11
    9. 0 0

    输出样例：

    1. 1
    2. 0
    3. 1
    4. 2
    5. 3
    6. 5
    7. 144
    8. 51205

     

      * dp[i][j] : 第 i-1 列摆好，方块从i-1列伸到第i列时，第i列的状态为j（j用二进制
     * 表示，第 1 位为0表示第0行没有方块从i-1 列伸到第i列，反之为1表示第0行有方块从
     * 第 i-1 列伸到第i列；
     *
     * dp[i][j] = dp[i][j] + dp[i-1][k]; k表示从第i-1列的方块能伸到第i列的合法的状
     * 态；
     *
     * 同时我们需要考虑两点：
     *  1）i-1列上同一行的格子,即a[i-1][k],k取一时，i-2列的第k行给予i-1的第k行的1
     *  不能与 i-1列的第k行伸到第i列的第k行的1同时满足，即i-1列上第k行的这个格子
     * 不能叠放两块方块，只能满足其一；
     *  2）同一列上不同行（这里指此时行的状态是1）之间的空格是用来放竖着的方块的，
     * 但是由于方块的长度是偶数，所以同一列上不同行之间的空格（这里指此时行的状态
     * 是1）必须满足偶数才合理；
     *
     * 满足这两个条件即可运用状态转移方程直接运算；同时初始化和答案是什么？
     * dp[0][0] = 1，此时从定义出发能够知道：dp[0][0] 表示从-1列伸到第i列的方格，
     * 每行的状态是0，即所有行都是竖着放的，只有这么一种状态；
     *
     * 答案即是：dp[m][0]: 从定义出发能够知道，dp[m][0] 表示将前m-1列全部摆好，且
     * 从m-1列的方格伸到第m列的方格，每行的状态是0，即从m-1列没有任何方格伸到第m列。

    first coding :

    1. /**
    2.  * dp[i][j] : 第 i-1 列摆好，方块从i-1列伸到第i列时，第i列的状态为j（j用二进制
    3.  * 表示，第 1 位为0表示第0行没有方块从i-1 列伸到第i列，反之为1表示第0行有方块从
    4.  * 第 i-1 列伸到第i列；
    5.  * 
    6.  * dp[i][j] = dp[i][j] + dp[i-1][k]; k表示从第i-1列的方块能伸到第i列的合法的状
    7.  * 态；
    8.  * 
    9.  * 同时我们需要考虑两点：
    10.  *  1）i-1列上同一行的格子,即a[i-1][k],k取一时，i-2列的第k行给予i-1的第k行的1
    11.  *  不能与 i-1列的第k行伸到第i列的第k行的1同时满足，即i-1列上第k行的这个格子
    12.  * 不能叠放两块方块，只能满足其一；
    13.  *  2）同一列上不同行（这里指此时行的状态是1）之间的空格是用来放竖着的方块的，
    14.  * 但是由于方块的长度是偶数，所以同一列上不同行之间的空格（这里指此时行的状态
    15.  * 是1）必须满足偶数才合理；
    16.  * 
    17.  * 满足这两个条件即可运用状态转移方程直接运算；同时初始化和答案是什么？
    18.  * dp[0][0] = 1，此时从定义出发能够知道：dp[0][0] 表示从-1列伸到第i列的方格，
    19.  * 每行的状态是0，即所有行都是竖着放的，只有这么一种状态；
    20.  * 
    21.  * 答案即是：dp[m][0]: 从定义出发能够知道，dp[m][0] 表示将前m-1列全部摆好，且
    22.  * 从m-1列的方格伸到第m列的方格，每行的状态是0，即从m-1列没有任何方格伸到第m列。
    23. */
    24.  
    25. #include <iostream>
    26. #include <cstring>
    27. #include <algorithm>
    28.  
    29. using namespace std;
    30.  
    31. typedef long long LL;
    32.  
    33. const int M = 12,N = 1 << M;
    34. LL dp[M][N];    //避免int溢出，数组需要开到 long long ;
    35. bool st[N];     
    36. //每一列的每行状态为i时，是否合法，即每两行从前一列有格子伸到
    37. //此列时，中间的空格是否为偶数，是则合理，否则不合理；
    38.  
    39. int main()
    40. {
    41.     int n,m;
    42.     while(cin >> n >> m , n || m)
    43.     {
    44.         
    45.         // 求st数组的值，初始化
    46.         for(int i=0;i < (1<<n) ; ++i)
    47.         {
    48.             bool isvaild = true;
    49.             int cnt = 0;
    50.             
    51.             for(int j=0;j < n;++j)
    52.             {
    53.                 // i的第j位是否为1
    54.                 if( i & (1<<j) ) 
    55.                 {
    56.                     //两个1之间0的个数
    57.                     if( cnt & 1 )
    58.                     {
    59.                         isvaild = false;
    60.                         break;
    61.                     }
    62.                 }
    63.                 else
    64.                     cnt++;  //i的第j位不是1，则0的个数加1
    65.             }
    66.             if(cnt & 1) //结束循环也得判断一下0的个数是否为偶数，
    67.                 isvaild = false;    //如果不是偶数个0，则不合理；
    68.             st[i] = isvaild;
    69.         }
    70.         
    71.         fill(*dp,*dp+N*M,0);    //输入不止一组数据，每次都要初始化
    72.         dp[0][0] = 1;   //初始化
    73.         
    74.         
    75.         for(int i=1;i <= m;++i) //m列
    76.         {
    77.             for(int j=0;j < (1<<n) ;++j)
    78.                 for(int k=0;k < (1<<n) ;++k)
    79.                 {
    80.                     //st数组表示某种状态下是否可行，第i-1列时的状态，不仅需要
    81.                     //考虑i-1列伸到第i列的状态，还要考虑i-2列伸到i-1列的状态，
    82.                     //那么两列状态都需要考虑时，就是两种状态按位加就是此时
    83.                     //i-1列的状态；
    84.                     
    85.                     //(j & k) ==0 i-1列上同一行的格子,即a[i-1][k],k取一时，
    86.                     //i-2列的第k行给予i-1的第k行的1不能与 i-1列的第k行伸到
    87.                     //第i列的第k行的1同时满足，即i-1列上第k行的这个格子
    88.                     //不能叠放两块方块，只能满足其一；
    89.                     if( st[j | k] && (j&k) ==0)
    90.                         dp[i][j] += dp[i-1][k];
    91.                 }
    92.         }
    93.         
    94.         cout << dp[m][0] << endl;
    95.     }
    96. }

    second coding:

    将能够从i-1列的状态  k 能够合法转移到 第i列的 状态 j ，先预处理出来：

    1. /**
    2.  * dp[i][j] : 第 i-1 列摆好，方块从i-1列伸到第i列时，第i列的状态为j（j用二进制
    3.  * 表示，第 1 位为0表示第0行没有方块从i-1 列伸到第i列，反之为1表示第0行有方块从
    4.  * 第 i-1 列伸到第i列；
    5.  * 
    6.  * dp[i][j] = dp[i][j] + dp[i-1][k]; k表示从第i-1列的方块能伸到第i列的合法的状
    7.  * 态；
    8.  * 
    9.  * 同时我们需要考虑两点：
    10.  *  1）i-1列上同一行的格子,即a[i-1][k],k取一时，i-2列的第k行给予i-1的第k行的1
    11.  *  不能与 i-1列的第k行伸到第i列的第k行的1同时满足，即i-1列上第k行的这个格子
    12.  * 不能叠放两块方块，只能满足其一；
    13.  *  2）同一列上不同行（这里指此时行的状态是1）之间的空格是用来放竖着的方块的，
    14.  * 但是由于方块的长度是偶数，所以同一列上不同行之间的空格（这里指此时行的状态
    15.  * 是1）必须满足偶数才合理；
    16.  * 
    17.  * 满足这两个条件即可运用状态转移方程直接运算；同时初始化和答案是什么？
    18.  * dp[0][0] = 1，此时从定义出发能够知道：dp[0][0] 表示从-1列伸到第i列的方格，
    19.  * 每行的状态是0，即所有行都是竖着放的，只有这么一种状态；
    20.  * 
    21.  * 答案即是：dp[m][0]: 从定义出发能够知道，dp[m][0] 表示将前m-1列全部摆好，且
    22.  * 从m-1列的方格伸到第m列的方格，每行的状态是0，即从m-1列没有任何方格伸到第m列。
    23. */
    24.  
    25. //将能够从i-1列的状态  k 能够合法转移到 第i列的 状态 j ，先预处理出来：
    26. #include <iostream>
    27. #include <cstring>
    28. #include <algorithm>
    29.  
    30. using namespace std;
    31.  
    32. typedef long long LL;
    33.  
    34. const int M = 12,N = 1 << M;
    35. LL dp[M][N];    //避免int溢出，数组需要开到 long long ;
    36. bool st[N];     
    37. //每一列的每行状态为i时，是否合法，即每两行从前一列有格子伸到
    38. //此列时，中间的空格是否为偶数，是则合理，否则不合理；
    39.  
    40. vector<int> state[N];
    41.  
    42. int main()
    43. {
    44.     int n,m;
    45.     while(cin >> n >> m , n || m)
    46.     {
    47.         
    48.         // 求st数组的值，初始化
    49.         for(int i=0;i < (1<<n) ; ++i)
    50.         {
    51.             bool isvaild = true;
    52.             int cnt = 0;
    53.             
    54.             for(int j=0;j < n;++j)
    55.             {
    56.                 // i的第j位是否为1
    57.                 if( i & (1<<j) ) 
    58.                 {
    59.                     //两个1之间0的个数
    60.                     if( cnt & 1 )
    61.                     {
    62.                         isvaild = false;
    63.                         break;
    64.                     }
    65.                 }
    66.                 else
    67.                     cnt++;  //i的第j位不是1，则0的个数加1
    68.             }
    69.             if(cnt & 1) //结束循环也得判断一下0的个数是否为偶数，
    70.                 isvaild = false;    //如果不是偶数个0，则不合理；
    71.             st[i] = isvaild;
    72.         }
    73.         
    74.         // 求state的值：
    75.         for(int j=0;j < (1<<n) ; ++j)
    76.         {
    77.             state[j].clear(); //输入不止一组数据，每次都要初始化
    78.             
    79.             for(int k=0;k < (1<<n) ; ++k)
    80.             {
    81.                 //st数组表示某种状态下是否可行，第i-1列时的状态，不仅需要
    82.                 //考虑i-1列伸到第i列的状态，还要考虑i-2列伸到i-1列的状态，
    83.                 //那么两列状态都需要考虑时，就是两种状态按位加就是此时
    84.                 //i-1列的状态；
    85.                 
    86.                 //(j & k) ==0 i-1列上同一行的格子,即a[i-1][k],k取一时，
    87.                 //i-2列的第k行给予i-1的第k行的1不能与 i-1列的第k行伸到
    88.                 //第i列的第k行的1同时满足，即i-1列上第k行的这个格子
    89.                 //不能叠放两块方块，只能满足其一；
    90.                 if( st[ j | k ] && ( j & k ) == 0 )
    91.                     state[j].push_back(k);
    92.             }
    93.         }
    94.         
    95.         fill(*dp,*dp+N*M,0);    //输入不止一组数据，每次都要初始化
    96.         dp[0][0] = 1;   //初始化
    97.         
    98.         
    99.         for(int i=1;i <= m;++i) //m列
    100.         {
    101.             for(int j=0;j < (1<<n) ;++j)
    102.                 for(auto k:state[j])
    103.                     dp[i][j] += dp[i-1][k];
    104.         }
    105.         
    106.         cout << dp[m][0] << endl;
    107.     }
    108. }

  • 相关阅读:
    Java为什么不直接实现Iterator接口，而是实现Iterable？
    [NLP] LLM---＜训练中文LLama2(四)方式一＞对LLama2进行SFT微调
    centos7 安装gcc boost 、cmake
    【强化学习论文合集】AAAI-2021 强化学习论文
    【debug】安装diffusion的bug解决合集
    笔试题积累
    全网最牛批的java八股面试文（针对秋招）堪称2022最强
    深入浅出 -- 系统架构之微服务标准组件及职责
    知道创宇上榜CCSIP 2022全景图多个领域
    人工智能如何改变联络中心座席
  • 原文地址：https://blog.csdn.net/qq_51825761/article/details/127017514