Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- // CSES DP - Removing Digits - https://cses.fi/problemset/task/1637/
- void getMinStepsToZero(int n, int steps, int &_min){
- if(n == 0){
- _min = min(steps, _min);
- return;
- }
- int temp = n;
- while(temp){
- int option = temp % 10;
- if(option != 0 && n - option >= 0){
- getMinStepsToZero(n - option, steps + 1, _min);
- }
- temp /= 10;
- }
- }
- int getMinStepsToZeroMemo(int n, vector<int> &memo){
- if(n == 0){
- return 0;
- }
- if(memo[n] != INT_MAX){
- return memo[n];
- }
- int temp = n;
- int minAtEachLevel = INT_MAX;
- while(temp){
- int option = temp % 10;
- if(option != 0 && n - option >= 0){
- minAtEachLevel = min(minAtEachLevel, 1 + getMinStepsToZeroMemo(n - option, memo));
- }
- temp /= 10;
- }
- return memo[n] = minAtEachLevel;
- }
- int getMinStepsToZeroDP(int n){
- //Storage & Meaning - dp[i] = Minimum steps required from i to 0
- vector<int> dp(n + 1, INT_MAX);
- // Direction - smallest problem at dp[0] - minimum step to reach 0 from 0;dp[0] = 0
- // largest problem at dp[n] - minimum step to reach 0 from n
- dp[0] = 0;
- // Travel & Solve - Travel from smallest to largest subproblem, building the solution way up
- for(int i = 1; i <= n; i++){
- int temp = i;
- while(temp){
- int option = temp % 10;
- if(option != 0){
- dp[i] = min(dp[i], 1 + dp[i - option]);
- }
- temp /= 10;
- }
- }
- return dp[n];
- }
- int main() {
- // your code goes here
- int n;
- cin >> n;
- int _min = INT_MAX;
- // getMinStepsToZero(n, 0, _min);
- // cout << _min << '\n';
- vector<int> memo(n + 1, INT_MAX);
- cout << getMinStepsToZeroMemo(n, memo) << '\n';
- cout << getMinStepsToZeroDP(n) << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
