AT360 雨上がり 动态规划

思路：我们用dp[i]来表示第i个元素存走到i时最少经过的水坑数。
dp[i]明显可以从 i-1 i-2 i-3得来。那么我们肯定要走跨过水坑数最小的那一条PATH，所以我们每次可以从这3条路径中找出最小的一条路径+判断当前的目的地是否有水坑。

核心代码

for(int i = 4; i <= n; i++)
        dp[i] = dp[i]+min(min(dp[i - 3], dp[i - 2]), dp[i - 1]);

/**
* From:
* Qingdao Agricultural University
* Created by XiangwangAcmer
* Date : 2019-10-03-18.21.09
* Talk is cheap.Show me your code.
*/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<cctype>
#include<stack>
#include<map>
#include<string>
#include<cstdlib>
#define ll long long
using namespace std;
const ll maxn = 1e6 + 5;
const ll minn = 1e9 + 5;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
const long long LIMIT = 4294967295LL;
vector<int>v[maxn];
int dp[maxn];
vector<int>G[maxn];
bool row[maxn], col[maxn];
bool flag = 0;
char a[maxn];
queue<int>q;
int main() {///dp[i]///第i个元素存走到i时最少经过的水坑数
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        if(a[i] == 'X')
            dp[i] = 1;
    }
    for(int i = 4; i <= n; i++)
        dp[i] = dp[i]+min(min(dp[i - 3], dp[i - 2]), dp[i - 1]);
    cout << dp[n] << endl;
    return 0;
}