So I was watching Errichto stream if At Coder Educational DP contest. I understood the transition and the base case but not the filling order. I tried messing with the order of the 3 nested for loops to fill up the table. Some permutations work and some don't .I was just wondering if anyone can help me understand why is that when you make the smaller_taken : {false, true} as the innermost loop we get wrong answer but when it is the second or the outer loop we get correct answer ?

Also I have another question in general to you all. Do you guys just test all orders, see which one passes test cases and then submit that or do you like spend time figuring out the details.

Now I do understand when the transition expression is something like dp[l] = l * dp[l-1] then clearly you need to fill from left to right but that's not always the case. So how do you go about it ?

Problem: https://atcoder.jp/contests/dp/tasks/dp_s

Solution (from the video lecture):

#include <bits/stdc++.h>

#define forn(i, n) for(int i=0; i<n; ++i)

using ll = long long;

using namespace std;

const int mod = 1e9 + 7;

void add_self(int &a, int b) {
	a += b;
	if(a >= mod)
		a -= mod;
}

void solve() {
	
	string k;
	cin >> k;

	int D;
	cin >> D;

	int len = k.size();

	vector<vector<int>>dp(D, vector<int>(2));

	dp[0][0] = 1;

	for(int where = 0; where < len; ++where) {
		vector<vector<int>> new_dp(D, vector<int>(2));

		for(int sum = 0; sum < D; ++sum) {	
			for(bool smaller_taken: { false, true }) {	// this cannot be made innermost for loop why?			
				for(int digit = 0; digit < 10; ++digit) {	

					if(digit > (k[where] - '0') && !smaller_taken) {
						break;
					}

					add_self(new_dp[(sum+digit) % D][smaller_taken || digit < (k[where] - '0')],
					 	dp[sum][smaller_taken]);
				}
			}
		}

		dp = new_dp;
	}

	int answer = (dp[0][false] + dp[0][true]) % mod;
	--answer;
 
	if(answer == -1)
		answer = mod - 1;

	cout << answer << "\n";

}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	// int t;
	// cin >> t;

	// while(t--)
		solve();
	
}

Errichto's YouTube channel Stream link: https://youtu.be/FAQxdm0bTaw?t=11154

Also wanna mention that I like this iterative solution than the recursive ones that exist out there on the internet.