本文共 1043 字，大约阅读时间需要 3 分钟。
dp[i][j]表示第i位之前和等于j的数
得公式dp[i][j] = dp[i][j] + dp[i-1][j-k]；
k为当前位上的数
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #define INF 1e718 #define MAXN 10001019 #define maxn 100001020 #define Mod 100000721 #define N 101022 using namespace std;23 typedef long long LL;24 25 int dp[11][111];26 int s, i, j;27 28 void run()29 {30 int ans = 0;31 if (s != 1)32 {33 for (i = 1; i<10; i++)34 ans += dp[i][s];35 cout << ans << endl;36 }37 else38 cout << 10 << endl;39 }40 41 int main()42 {43 int i, j;44 for (i = 1; i<10; i++)45 dp[1][i] = 1;46 for (i = 1; i <= 9; i++)47 for (j = 1; j <= 9 * i; j++)48 for (int k = 0; k <= 9 && k <= j; k++)49 dp[i][j] += dp[i - 1][j - k];50 while (cin >> s)51 run();52 //system("pause");53 return 0;54 }
转载于:https://www.cnblogs.com/usedrosee/p/4356838.html