注册 登录
编程论坛 C++教室

石子合并问题(求助 改错)

diaoxue 发布于 2007-12-22 20:58, 1203 次点击
一列石子,公式得到了,用动态规划实现时总是输出0
我实现矩阵连乘算法用动态规划也不能得到正确结果
[code=c]
/*m[i][j]={0 i=j;min{m[i][k-1]+m[k][j]+w(i,j)} i<j}*/
#include <iostream>
using namespace std;
const int N=4;
int a[N]={4,4,5,9};
int m[N][N]={0};
int s[N][N]={0};
int Sum(int a[],int i,int j)//最后一次合并的得分
{
    int temp=0;
    for(int k=i;k<=j;k++)
    {
        temp+=a[k];
    }   
    return temp;
}

void Stone()//动态规划求最小得分
{
    int i,j,r,k,t;
    for(i=0;i<N;i++)
        m[i][i]=0;
    for(r=1;r<N;r++)
    {
        for(i=0;i<N-r;i++)
        {
            j=i+r;
            for(k=i+1;k<j;k++)
            {
                t=m[i][k-1]+m[k][j]+Sum(a,i,j);
                if(t<m[i][j])
                {
                    m[i][j]=t;
                    s[i][j]=k;
                }   
            }   
        }   
    }     
}
        
int main()
{
    Stone();  
    cout<<m[0][N-1]<<endl;  
    return 0;
}    [/code]
2 回复
#2
HJin2007-12-23 04:11
i did NOT read your code line by line. I saw you have a formula at the beginning of the code and I guess you are implementing the formula.

My experience with DP is that you may need some boundary conditions, say

m[i][0] = 0 for all i // i.e., first column is 0
m[0][j] = 0 for all j // 1st row is 0

besides m[i][i] = 0

I may be wrong. But this is my point of view.
#3
aipb20072007-12-23 10:42
把题目连接给出来,就有人给你做做看了!
1