DP f和g - wenzhoullq/leetcode GitHub Wiki
f和g
一般返回两个值,分别是f和g,f表示的是路径的XX值，g表示的路径的个数，可以压缩到一次循环即可
int[][] dp = new int[leny+1][lenx+1],cnt=new int[leny+1][lenx+1];
cnt[1][1] = 1;//注意路径个数的初始化
for(int i = 1 ; i <= leny ;i++ ){
for(int j = 1; j <=lenx ;j++){
int max = Math.max(Math.max(dp[i-1][j-1],dp[i][j-1]),dp[i-1][j]);
if(m[i][j]=='X'||(cnt[i-1][j]==0&&cnt[i][j-1]==0&&cnt[i-1][j-1]==0)) continue;//注意continue的情况,如果没有一条之前的路，果断continue
int num = m[i][j] - '0';
dp[i][j] = max+num;
if(dp[i][j-1]==max) cnt[i][j] = (cnt[i][j]+cnt[i][j-1])%mod;
if(dp[i-1][j]==max) cnt[i][j] = (cnt[i][j]+cnt[i-1][j])%mod;
if(dp[i-1][j-1]==max) cnt[i][j] = (cnt[i][j]+cnt[i-1][j-1])%mod;
}
}
return new int[]{dp[leny][lenx],cnt[leny][lenx]};