meta user
network profile
| bio | website | bitsteller.blogspot.com |
|---|---|---|
| location | Germany | |
| age | 29 | |
| visits | member for | 7 months |
| seen | May 3 at 7:09 | |
| stats | profile views | 9 |
I'm ashamed to confess that I edited this page just to get another bronze badge ...
|
Nov 22 |
awarded | Benefactor |
|
Nov 22 |
comment |
How to prove that a dynamic programming algorithm is a monotonic function Sorry for awarding the bounty so late. I thought you get the points automatically when I accept your answer. |
|
Nov 21 |
awarded | Teacher |
|
Nov 16 |
revised |
How to prove that a dynamic programming algorithm is a monotonic function added 95 characters in body |
|
Nov 16 |
awarded | Scholar |
|
Nov 16 |
accepted | How to prove that a dynamic programming algorithm is a monotonic function |
|
Nov 16 |
answered | How to prove that a dynamic programming algorithm is a monotonic function |
|
Nov 15 |
comment |
How to prove that a dynamic programming algorithm is a monotonic function By the way, thanks for sticking with me ;) I really appreciate your help! |
|
Nov 15 |
comment |
How to prove that a dynamic programming algorithm is a monotonic function @user1151 You got me wrong. Let's say $MATCH(m-1,n-1) = 2$, $sim(a_m,b_n) = -1$, and the other cases are like you stated them. Then $MATCH(m-1,n-1)+sim(a_m,b_n) = 1$ and $max(1,0,0) = 1$ and therefore we found a counterexample because that means $MATCH(m-1,n-1) \gt MATCH(m,n)$. Again, by thinking through the recursion bottom up, I know that this can never happen, but I just cannot show it using my formula. |
|
Nov 15 |
comment |
How to prove that a dynamic programming algorithm is a monotonic function Yes, that is the definition, but what is still bugging me is that in the case of $MATCH(m-1,n-1) + sim(a_m,b_n)$ the expression $sim(a_m,b_n)$ could be negative, but the whole expression could still be greater than the other options. In this case it could be that $MATCH(m,n) \lt MATCH(m-1,n-1)$. I mean that will never be the case, but I don't know how to prove that. |
|
Nov 15 |
comment |
How to prove that a dynamic programming algorithm is a monotonic function I agree, by looking at the function, one concludes that the progression ought to be monotonic. But by writing $MATCH(m,n) \leq MATCH(m,n-1)$ you have not proved yet why $MATCH(m,n-1)$ must be smaller or equal than $MATCH(m,n)$. Or am I missing something? I'm really not that experienced when it comes to proofs, so bear with me ;) |
|
Nov 14 |
awarded | Promoter |
|
Nov 11 |
awarded | Editor |
|
Nov 11 |
revised |
How to prove that a dynamic programming algorithm is a monotonic function fixed some errors |
|
Nov 11 |
awarded | Student |
|
Nov 11 |
asked | How to prove that a dynamic programming algorithm is a monotonic function |
|
Nov 11 |
awarded | Autobiographer |
