[2688] 줄어들지 않아

https://www.acmicpc.net/problem/2688

2차원 DP로 정의하시면 쉽게 해결할 수 있습니다.

dp[자리수][현재 수]라고 정의하면 되겠습니당.

그리고 dfs안에서 포문은 자기 자신과 같거나 큰수로 이동하면 되겠습니다!!!!!!!!!!!!

코드입니당!~_~

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;
 
#define ll long long
#define MOD (ll)1e15
#define MAX_SIZE (int)1e5
#define mp make_pair
#define INF 987654321
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
 
ll dp[65][10];
int n;
 
ll f(int d, int now) {
    if (d == n) return 1;
 
    ll &ret = dp[d][now];
    if (ret != -1) return ret;
    ret = 0;
 
    for (int i = now; i < 10; i++) {
        ret += f(d + 1, i);
    }
 
    return ret;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    int t;
    cin >> t;
 
    while (t--) {
        memset(dp, -1, sizeof(dp));
 
        cin >> n;
 
        ll ret = 0;
        for (int i = 0; i < 10; i++) ret += f(1, i);
 
        cout << ret << '\n';
    }
    return 0;
}