- 科技
- leetcode：1301. 最大得分的路径数目（dp，困难）
题目：
分析：为什么要斜着走，向上，向左，多走一个不香吗？所以斜着走的原因只是上方&左方都是障碍。不过貌似没必要特殊去考虑。
一道困难的水题，
难点应该就是初始化吧。
代码：
class Solution {
public:
vector
<int> pathsWithMaxScore(vector
<string
>& b
) {
int A
[101][101];
int B
[101][101];
vector
<int> v(2,0);
if(b
.size()==0) return v
;
b
[b
.size()-1][b
[0].size()-1]='0';
b
[0][0]='0';
memset(A
,0,sizeof(A
));
memset(B
,0,sizeof(B
));
B
[b
.size()-1][b
[0].size()-1]=1;
for(int i
=b
[0].size()-2;i
>=0;i
--)
{
if(b
[b
.size()-1][i
]=='X') break;
A
[b
.size()-1][i
]=A
[b
.size()-1][i
+1]+b
[b
.size()-1][i
]-'0';
B
[b
.size()-1][i
]=1;
}
for(int i
=b
.size()-2;i
>=0;i
--)
{
if(b
[i
][b
[0].size()-1]=='X') break;
A
[i
][b
[0].size()-1]=A
[i
+1][b
[0].size()-1]+b
[i
][b
[0].size()-1]-'0';
B
[i
][b
[0].size()-1]=1;
}
for(int i
=b
.size()-2;i
>=0;i
--)
{
for(int j
=b
[0].size()-2;j
>=0;j
--)
{
if(b
[i
][j
]=='X') continue;
int maxx
=max(max(A
[i
+1][j
+1],A
[i
+1][j
]),A
[i
][j
+1]);
if(maxx
==A
[i
+1][j
+1])
{
B
[i
][j
]+=B
[i
+1][j
+1];
B
[i
][j
]=B
[i
][j
]%1000000007;
}
if(maxx
==A
[i
+1][j
])
{
B
[i
][j
]+=B
[i
+1][j
];B
[i
][j
]=B
[i
][j
]%1000000007;
}
if(maxx
==A
[i
][j
+1])
{
B
[i
][j
]+=B
[i
][j
+1];B
[i
][j
]=B
[i
][j
]%1000000007;
}
A
[i
][j
]=maxx
+b
[i
][j
]-'0';
}
}
v
[0]=(A
[0][0]);
v
[1]=(B
[0][0]);
if(v
[1]==0) v
[0]=0;
for(int i
=0;i
<3;i
++)
{
for(int j
=0;j
<3;j
++)
{
cout
<<A
[i
][j
]<<' ';
}
cout
<<endl
;
}
return v
;
}
};
还行：
Processed:
0.016, SQL:
9
