动态规划问题解题思路和总结

int solve(int i, int j){

return a[i][j] + (i == n ? 0 : max(solve(i+1,j),solve(i+1,j+1)));

}

int i, j;

for(j = 1; j <= n; j++) d[n][j] = a[n][j];

for(i = n-1; i >= 1; i--)

for(j = 1; j <= i; j++)

d[i][j] = a[i][j] + max(d[i+1][j],d[i+1][j+1]);

int solve(int i, int j){

if(d[i][j] >= 0) return d[i][j];

return d[i][j] = a[i][j] + (i == n ? 0 :

max(solve(i+1,j),solve(i+1,j+1)));

}

int dp(int i) {

int& ans = d[i];

if(ans > 0) return ans;

ans = 1;

for(int j = 1; j <= n; j++)

if(G[i][j]) ans = max(ans, dp(j)+1);

return ans;

}

void print_ans(int i) {

printf("%d ", i);