这个题，先来一个裸dfs看看能骗几分：
class Solution {
public:
long long num=0;
void dfs(vector<int>& locations, int start,int pre, int finish, int fuel ){
if(fuel < 0){
return ;
}
if(start==finish){
num++;
num=num%(1000000007);
return ;
}
int len=locations.size();
for (int i = 0; i < len; ++i) {
if(i!=start){
dfs(locations,i,start,finish,fuel-abs(locations[i] - locations[start]));
}
}
}
int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
dfs( locations, start, -1, finish, fuel);
return num;
}
};
诶呀呀，怎么才过了三个测试样例。，，
其实想想也是，如果fuel一多，这不就直接爆炸，跑过来跑过去的，飘了~~~~
那再考虑一下的话就是，当油量和所在位置一样的时候，其实路径是一样的，我们可以记录一下的嘛（dfs+记忆化搜索）
注意一个点，就是它就算到了终点也只是把结果+1而已，根本不需要return
class Solution {
public:
int num=0;
vector<int> lujing;
int mem[250][250];
int dfs(vector<int>& locations, int now, int finish, int fuel ){
if(fuel < 0){
return 0;
}
if(mem[now][fuel]!=-1){
return mem[now][fuel];
}
mem[now][fuel]=0;
if(now==finish){
mem[now][fuel]+=1;
mem[now][fuel]%=1000000007;
}
int len=locations.size();
for (int i = 0; i < len; ++i) {
int diff=abs(locations[i] - locations[now]);
if(i!=now && diff<=fuel){
mem[now][fuel]+=dfs(locations,i,finish,fuel-abs(locations[i] - locations[now]));
mem[now][fuel]%=1000000007;
}
}
return mem[now][fuel];
}
int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
memset(mem,-1,sizeof(mem));
return dfs( locations, start, finish, fuel);
}
};
昂，其实这样就过了
但是！！！据说记忆化搜索都可以变成dp，那为什么不,,,问一下神奇海螺呢？
其实这个时候我们的dp数组都已经出来了。就是刚刚dfs的时候用的那个数组，现在我们要做的是，根据dfs代码把他变成一个dp的解法。
第一维没有明确的大小关系，但是第二维油量，要求大油量依赖小油量，所以这一维应该是从低枚举的。
class Solution {
public:
int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
int mem[250][250]={0};
int len=locations.size();
memset(mem,-1,sizeof(mem));
for (int i = 0; i <= fuel ; ++i) {
mem[finish][i]=1;//这个是边界条件
}
for (int i = 0; i <= fuel ; ++i) {
for (int j = 0; j < len; ++j) {
for (int k = 0; k < len; ++k) {
if(j!=k) {
int need = abs(locations[j]-locations[k]);
if(i>=need){
mem[k][i]+=mem[j][i-need];//注意这个地方，mem[k]才是你要更新的
mem[k][i]%=1000000007;
}
}
}
}
}
return mem[start][fuel];
}
};