poj3230二维dp O（N^3）实现图上dp
【题意】：有n个城市，一个人从i到j城市时，可以得到income[j]的财富，需要消耗cost[i][j]的财富，也可以选择不动，也就是呆在i城市，那么可以得到income[i]的财富，需要消耗cost[i][i]的财富,但每个城市的incom[]是随天数变化的，求出m天内这个人能获得的最大的财富值。
【分析】：dp[i][j]表示第i天选择呆在j城市能累计得到的最多的money，每次根据新的一天的income计算dp即可
【代码】：
1 #include<iostream> 2 #include<string.h> 3 #include<stdio.h> 4 #define maxn 125 5 using namespace std; 6 7 int cost[maxn][maxn],w[maxn][maxn]; 8 int dp[maxn][maxn]; 9 int N,M; 10 int main(){ 11 while(cin>>N>>M){ 12 if (N==0 && M==0) break; 13 for(int i=1;i<=N;i++){//meiju N 14 for(int j=1;j<=N;j++) scanf("%d",&cost[i][j]); 15 } 16 for(int i=1;i<=M;i++){ 17 for(int j=1;j<=N;j++) scanf("%d",&w[i][j]); 18 } 19 memset(dp,-1,sizeof(dp)); 20 dp[0][1]=0;//dp[i][j]:ith day jth city 21 for(int i=1;i<=N;i++) dp[1][i]=-cost[1][i]+w[1][i]; 22 for(int i=2;i<=M;i++){//da 23 for(int j=1;j<=N;j++){//stay at jth city 24 for(int k=1;k<=N;k++){//from kth city 25 dp[i][j]=max(dp[i][j],dp[i-1][k]-cost[k][j]+w[i][j]); 26 } 27 } 28 } 29 int ans=-(1<<(30)); 30 for(int i=1;i<=N;i++){ 31 ans=max(ans,dp[M][i]); 32 } 33 cout<<ans<<endl; 34 } 35 return 0; 36 }