最近刚入手动态规划，发现作者貌似有点错误，分享出来，也不知道是我错，还是作者错，高手请鉴定之。
题目是:
给出n个硬币，计算出组成值为S的最多硬币个数和最少硬币个数。

作者用了3种方法，就不一一说了，只说这个所谓的记忆化搜索。

定义d(i)，组成面值为i所需要最少或最多枚硬币,也就是求最短和最长路问题。状态转义当然是d(i) = max(d(i - V[j]) + `1);
以下是作者代码

int dpmax(int s){
    if(vis[s]) 
        return d[s];
    vis[s] = 1;
    d[s] = -1 << 30;
    for(int i = 1; i <= n; i++){
        if(s >= V[i])
            d[s] >?= dpmax(s - V[i]) + 1;
    }
    return d[s];
}

读完后，就觉得好像哪里不太对劲，就是那一行d[s] = -1 << 30最后要是没找到，也就是没有发生状态转移，岂不是就返回-1 << 30。
要知道，这样子构造起来的d【s】的值一定错了啊。是不是？
我是这样想的，作者貌似忘记考虑，当到状态边界时，也就是目标状态d【0】时，返回的应该是0.

于是我修改为

int dpmax(int s){
    if(s == 0)
         return 0;
    if(vis[s]) 
        return d[s];
    vis[s] = 1;//记住 
    d[s] = -1 << 30;
    for(int i = 1; i <= n; i++){
        if(s >= V[i])
            d[s] >?= dpmax(s - V[i]) + 1;
    }
    return d[s];
}

我的代码运行后输出 10 2，观察下的确没错，但是作者的代码是输出不了正确结果。
测试数据:
10 10
4 3 2 6 8 1 2 3 11 13
输出:
10 2

楼主强大

过奖了。

dp[0]=0属于边界条件，所以在调用记忆化搜索之前就需要写明vis[0]=1,dp[0]=0，所以作者的这段记忆化搜索代码无误，但是可能他没注明边界条件

求知就是一条不断发现错误的道路...
哎呀~ 好文雅  好煽情~

嗯嗯嗯，是啊，这样也可以，都差不多~，看来我们都没错。这样写更好