codeforce1673C. Palindrome Basis_cf1673c palindrome basis

传送门：今天不学习，明天变辣鸡

简述一下题意：给出一个n，求有多少回文数相加的方式等于n。
其中4 = 1+2+1 和 4 = 2+1+1为一种相加方式，要求方式间至少要有一个数字不同，才能叫做不同方式。

首先，n<4e4的，而且还是仅考虑范围中的回文数，所以实际的数据量是很小的，不会超过1e3，所以写个最暴力的dp也才4e7的计算量，给2s的时间绝对够了。

怎么判断回文数见代码实现。

然后就是如何设计递推公式和dp数组了。这个我也没想出来，直接看的tutorial。
记dp[k][m]表示前m个回文数相加为k的方式数。这里m虽然限定范围在前m个，但是并不是m个数字都要使用。
递推公式：其中p_m为第m个回文数。

$$dp[k][m]=dp[k][m-1]+dp[k-p_m][m]$$

前m个回文数构成k，可由两个状态推导，前m-1个数组成k的方式数+前m个回文数组成k-p_m的方式数。不难看出，组成k的加数是有序的，所以不会出现重复的情况，也就是说只会有5=1+2+2,而不会出现5=2+1+2这种情况。
此外注意到递推式的最后一项，为什么是$d$