金币问题

今年某公司的笔试题：

一个矩阵地图，每一个元素值代表金币数，玩家从左上角一直走到右下角，每次只能向下移动一格或是向右移动无数格后向下移动一格。当元素值为-1时，玩家无法移动到此格。玩家每移动到一格就可以获取这一格的金币数，求获得最大金币数。
很容易的一道动态规划题，动态转移方程

m[i][j] = max{m[i-1][j] + a[i][j], m[i-1][k] + a[i-1][j] + a[i][j]}  0 <= k < j

初始化：

#define MIN -1000000
int a[M][N];//金币矩阵
int m[M][N];//最大值矩阵

void init(){
    memset(m,0,sizeof(int) * M * n);
    int i,j,k;
    int sum = 0;
    for(i = 0; i < M; i++){//初始化第一列
        if(a[i][j] == -1){
            m[i][0] = MIN;
        }else{
            sum+=m[i][0];
            m[i][0] = sum;
        }
    }
   
    for(j = 0; j < N; j++){//初始化第一行
        if(a[0][j] == -1){
            m[0][j] = MIN;
        }else{     
             m[0][j] = a[0][j];
        }
    }
}

 

 

 从底往上递推代码：

int max_coin(){
    int i,j,k;
    for(i = 1; i < M; i++)
        for(j = 1; j < N; j++){
            int max =  m[i-1][j] + a[i][j];
            for(k = 0; k < j; k++){
                int coins = m[i-1][k] + a[i-1][j] + a[i][j];
                if(coins > max)
                    max = coins;
            }
        }
    return m[M-1][N-1];
}

 

 

直接记事本的方式递归，发现已经计算过直接返回的方式：

   int max_coin(int i,int j){
        if(m[i][j] != 0)//已经计算出来
            return m[i][j];
        else{
            int max = max_coin(i-1,j) + a[i][j];
            for(int k = 0; k < j; k++){
                t_m = max_coin(i,k) + a[i-1][j] + a[i][j]);
                if(max <  t_m)
                    max = t_m;
            }
            return max;
        }
    }

 

 

评论

7 楼 lcwen08 2010-03-09  

"移动到一格才能得到金币，并不是移动经过的路径的金币都可以得到。"
原来如此，

6 楼 fuliang 2010-03-09  

lcwen08 写道

(i-1, k)点尽管最大，但它不一定能够到达(i-1, j)点..

这里将无法移动到的格设置到了一个最小值MIN，相当于负无穷，这样可以忽略掉不可到达的格子了，因为凡是移动到不可到达格的方案是不可能在求最大值中取胜的。

5 楼 fuliang 2010-03-09  

lcwen08 写道

不过，我又想了想，方程好像应该这样写：
m[i][j] = max { m[i-1][k] + a[i-1][k+1] + ... + a[i-1][j]} + a[i][j]
其中 (0 <= k < j),
这里：
int coins = m[i-1][k] + a[i-1][j] + a[i][j];
(i-1, k)点尽管最大，但它不一定能够到达(i-1, j)点..

这个可能是下面这句话你理解的偏差：

引用

玩家每移动到一格就可以获取这一格的金币数

移动到一格才能得到金币，并不是移动经过的路径的金币都可以得到。

4 楼 lcwen08 2010-03-09  

不过，我又想了想，方程好像应该这样写：
m[i][j] = max { m[i-1][k] + a[i-1][k+1] + ... + a[i-1][j]} + a[i][j]
其中 (0 <= k < j),
这里：
int coins = m[i-1][k] + a[i-1][j] + a[i][j];
(i-1, k)点尽管最大，但它不一定能够到达(i-1, j)点..

3 楼 lcwen08 2010-03-09  

哈哈，明白了，原来每次都必须得向下移动一格啊

2 楼 fuliang 2010-03-09  

lcwen08 写道

我是初学者，可能考虑的有问题，请指教：
如果m[i][j-1] > m[i-1][j]，是不是要取:
   m[i][j] = m[i][j-1] + a[i][j] ？
解法中好像不是啊..

从m[i][j-1]到m[i][j]是不可达的，所以没有你说的那种情况，原因是题目中说：
每次只能向下移动一格或是向右移动无数格后向下移动一格

1 楼 lcwen08 2010-03-09  

我是初学者，可能考虑的有问题，请指教：
如果m[i][j-1] > m[i-1][j]，是不是要取:
   m[i][j] = m[i][j-1] + a[i][j] ？
解法中好像不是啊..