I was watching this lecture from MIT on dynamic programming, at the 22nd minute, the lecturer said that the formula for calculating the time complexity for a recursive dynamic programming solution using memoization is equal to the number of subproblems * the time of each subproblem without the recursive work.

I am having trouble understanding why this formula is true.

I understand the time complexity of a bottom-up solution because the loops make it obvious, but this top-down using memoization I find a bit confusing.

So if anyone cane share an intuitive way of understanding this formula it would be great.

Thank you in advance.

I recently learnt about the Fenwick Tree data structure and i understand how everything works and how it is implemented.

Now my issue is in the point update algorithm:

I understand why adding the LSB to a number would get us the next number with a range that also contains/covers the current number we are on. This is because adding any number less than the LSB won’t work, as well as a number with the same LSB can not cover our current number either (Proof in this article). Therefore the only possible option left is a number with a greater LSB, and to get the smallest such number this can be done by adding the LSB to the current number, and I understand why this number will always cover the previous number we were on.

Now what I can’t see is why adding the LSB again to the number we moved on to would also get us the next range that we need to update. I tried reading this article with the same question but I could not find any useful answer.

If anyone can help me with this I would really appreciate it because personally it doesn’t feel right using something without understanding why it works.

Thank you in advance.

I was solving this problem Odd Divisor and when I tested it using the sample test cases it produced the correct output in my IDE, however when I submit the code, it produces a different output with the sample test case and so gives a wrong answer on test 1.

Here's the code:

#include <iostream>
#include <string>
using namespace std;


long t, x;
int main(){


    cin >>t;
    while(t--){
        cin>>x;
        if(x%2==1)cout<<"YES";
        else{
            bool f=false;
            while(x>1){
                if((x/2)%2==1&&(x/2)!=1){
                    f=true;
                    break;
            }
            x/=2;
        }
        if(f)cout<<"YES";
        else cout<<"NO";
    }
    cout<<"\n";
}
return 0;
}

If anyone knows why this is happening, I would really appreciate the help.