c++ - 最小成本总和

Question

我想计算给定二维数组中的最小和

#include<iostream>
#include<limits.h>
using namespace std;
#define R 3
#define C 3
int Min(int x,int y,int z){
   if(x<y){
        return (x<z)?x:z;
   }
   else
       return (y<z)?y:z;
   }
int mincost(int cost[R][C],int m,int n){

    int i,j;
    int t[R][C];
    t[0][0]=cost[0][0];
    for(i=1;i<=m;i++)
        t[i][0]=t[i-1][0]+cost[i][0];
    for(j=1;j<=n;j++)
t[0][j]=t[0][j-1]+cost[0][j];
    for(i=1;i<=m;i++){
        for(j=1;j<=n;j++){
            t[i][j]=Min(t[i-1][j-1],t[i-1][j],t[i][j-1]+cost[i][j]);
        }
    }
      return t[m][n];

}

int main(){

    int cost[R][C]={{1,2,3},
                    {4,8,2},
                    {1,5,3}};
    cout<<mincost(cost,2,2)<<endl;


    return 0;
}

对于这个数组，从起点 (0,0) 到某个点 (m,n) 等于 8，但输出显示 1，为什么？这段代码有什么问题？文字算法

Given a cost matrix cost[][] and a position (m, n) in cost[][], write a function that returns cost of minimum cost path to reach (m, n) from (0, 0). Each cell of the matrix represents a cost to traverse through that cell. Total cost of a path to reach (m, n) is sum of all the costs on that path (including both source and destination). You can only traverse down, right and diagonally lower cells from a given cell, i.e., from a given cell (i, j), cells (i+1, j), (i, j+1) and (i+1, j+1) can be traversed. You may assume that all costs are positive integers.

Answer 1

我看到这是一个动态规划解决方案。

这里有错别字:

t[i][j]=Min(t[i-1][j-1],t[i-1][j],t[i][j-1]+cost[i][j]);

应该是:

t[i][j]=Min(t[i-1][j-1],t[i-1][j],t[i][j-1]) + cost[i][j];

基本上它的工作方式类似于 t[i][j] = t[i-1][j-1]。

注意:调试这些问题的一个好方法是打印中间矩阵(此处:t)。