<dp> hdoj 2571 命运

本来不会的，在队友细心指导下做出来了！开心！

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=2571

解题思路：
裸dp
先建个二维num存数据，
（我定义越往右下，辈分越小，即左上是爸爸，右下是儿子）
二维dp存这个位置下的由父亲过来的最大数值
根据“下一步可以是（x+1,y），(x,y+1)或者(x,y*k) 其中k>1。 ”
先注意边界处理dp为-inf，01和10坐标的dp取0，致使后面循环条件方便
双层循环取相邻最大的爸爸
即temp=max(dp[i-1][j]+num[i][j],dp[i][j-1]+num[i][j]);
再利用循环找左边跳过来的因数爸爸
之后这俩（三）爸爸取最大值作为当前未知的dp值
最后输出终点位置的的dp值

AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,num[25][1005],dp[25][1005];
const int inf=99999999;
//num储存当前位置的数据，dp存到达此位置时最高幸运值 

int main()
{
    int c;
    cin>>c;
    
    while(c--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>num[i][j];
        
        memset(dp,0,sizeof(dp)); 
         
        int line=max(n,m); 
        for(int i=0;i<=n;i++)           //边界控制，这样后顾无忧 
            dp[i][0]=-inf;
        for(int j=0;j<=m;j++)           
            dp[0][j]=-inf;

        dp[0][1]=0,dp[1][0]=0;          //这个是为了后续num[1][1]不受边界干扰 
        
        //下一步可以是（x+1,y），(x,y+1)或者(x,y*k) 其中k>1。      
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                
                int temp1=dp[i-1][j]+num[i][j];         //temp1:他的父亲是上位
                int temp2=dp[i][j-1]+num[i][j];         //temp2:他的父亲是左邻位 
                int MAX=max(temp1,temp2);
                
                int temp3=-inf;
                for(int tj=1;tj<j;tj++)                 //temp3:他的父亲是左因数位  
                    if(j%tj==0)
                        temp3=max(temp3,dp[i][tj]+num[i][j]);
                
                dp[i][j]=max(MAX,temp3);
                 
            }
        } 
        
        printf("%d\n",dp[n][m]);
        
    }
    return 0;
}