Matrix problem, the path that is the flattest
Don't take this the wrong way, but my first thought when I looked at your code was "ugh do I really want to read this?"  You have (probably) been thinking a lot about A, S, n, and D over the last few hours, but if you look at this again in 2 years, it will look like nonsense.  So your number one goal should be to fix readability.  Then you can start thinking about correctness and performance.

I would recommend reading through a C++ style guide for general tips.  Here is one, but there are many others.  I'll still list a few of the biggest mistakes:


You should avoid single letter variable names
Try to express your logic in functions
Don't use global variables
Indent consistently (or better yet, automatically with help from your IDE)


All of these have been written about extensively in style guides, programming manuals, other code reviews, etc...



fin&gt;&gt;n;


What if n &gt; 21?  If you have some reason to believe it cannot be, then you should assert(n &lt; 22).  But in this case, it's easy enough to support any n with std::vector.



i&lt;=n-1


The canonical way to write this is i &lt; n.



`S[i-1][j]+abs(A[i][j]-A[i-1][j])`


I think this section is correct, but I have more style comments!


This is complicated looking for no reason.  You're making yourself think harder than you have to which means you will accomplish less stuff with your mental bandwidth.  How about something like costOfStep(i-1, j)?
This gets exactly repeated twice and a very similar statement is also repeated twice.  That's a telltale sign you should at least use a variable or better yet write a function to compute this.


Isn't the snipped below easier to read?

for(int i = 1; i &lt; n; i++) {
    for(int j = 1; j &lt; n; j++) {
        int costOfStepDown = costOfStep(i - 1, j);
        int costOfStepRight = costOfStep(i, j - 1);
        minCosts[i - 1][j] = std::min(costOfStepDown, costOfStepRight);
    }
}




//a new matrix to identify the path and memorize the down/right moves
int i,j,x;
i=n-1;
j=n-1;
x=1;


From this point on, I think you are using more time/memory than necessary.  I believe you can refactor your code so that you only store one matrix for both the input array and one for the cumulative array (or two matrices if it's clearer, but not more).  And you can store your path as a 1D vector.  Doing two passes leads to unnecessary code which leads to pointless bugs and wasted time.  Keep it minimal!  You were following a decently minimal algorithm until this part...

Also, here are my thoughts while reading this snippet:


Nice a comment... Where is the new matrix?
Oh some single named variables.  No idea what these do.  Hopefully I can figure it out.
Huh they are not initialized.  I hope the author was careful not to use uninitialized values.


That's a lot of thinking for not very much action.  How about this:

Matrix path;
path[0][0] = inputMatrix[size - 1][size - 1];
for (int i = 0, j = 0; i &lt; size &amp;&amp; j &lt; size; /*increment in body*/) {
    ...




This is more of a general tip than a specific comment.  I hope you find it useful.

Many dynamic programming problems are easy to solve with recursion.  Here's some pseudo-code for this problem:

// return the min cost of traveling from pos to the bottom-right of inputMatrix
int minCost(Matrix const&amp; input, Position const pos = top-left) {
    if (pos == bottom-right) {
        return 0;
    }
    return std::min(minCost(input, pos.right), minCost(input, pos.down));
}


Position could be std::pair&lt;int, int&gt; and Matrix could be std::vector&lt;std::vector&lt;int&gt;&gt;.

This function will calculate the correct answer, but it is slow because it repeatedly calculates the min cost of the same position many times.  Fix that:

int minCostHelper(Matrix const&amp; input, Position const pos, Cache cache) {
    if (cache.hasSeen(pos)) {
        return cache.valueOf(pos);
    }
    if (pos == bottom-right) {
        return 0;
    }
    auto result = std::min(minCost(input, pos.right), minCost(input, pos.down));
    cache.insert(pos, result);
    return result;
}

int minCost(Matrix const&amp; input) {
    Cache cache;
    return minCostHelper(input, top-left, cache);
}


Cache could be an std::map.

The technical term for "fix" in this case is "memoize."  I think this style is easier to read/debug than manually creating arrays.  It's a question of personal preference though.

Here is a challenge: can you write a function that will memoize another function?

template &lt;typename Function&gt;
Function memoize(Function);