简单动态规划题

题目简述

n * m 的方格，每一个都有一个能量值，初始在左上角，终点在右下角，初始能量就是起点方格的能量值。每步只能向右或向下走一格，一步消耗1能量，一次可以走若干步，只有一次走完后才更新能量，中间经过的方格能量无效；

每走一次，能量清零，新的初始能量为当前方格的能量值。求有多少种不同的路径从左上角到达右下角（按顺序依次到达的点只要有一个不同时，就视为不同的路径），答案对10000取余。

算法分析

题面又臭又长，很是唬人，其实就是个简单dp题。 简单来说，本题就是求从 [0][0] 到 [n-1][m-1] 的方案数目， dfs 的递归思想。

记从 [0][0] 到 [x][y] 的方案数目为 dp[x][y]，则由回溯思想知：

若能从 [tx][ty] 到达 [x][y] ，则 dp[x][y] 就是所有的 dp[tx][ty] 的累加和。

那我们就简单的从左上往右下更新 dp 数组的值即可。

C++代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int No8_dp(vector<vector<int>>& energy) {
        const int mod = 10000;
        int n = energy.size(), m = energy[0].size();
        // dp[i][j]表示从(0,0)到达(i,j)的方案数
        vector<vector<int>>dp(n, vector<int>(m, 0));
        dp[0][0] = 1;
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < m; y++) {
                int cur = energy[x][y];
                int mi = min(cur, n - 1 - x);
                for (int i = 0; i <= mi; i++) {     // 向下走i步
                    int mj = min(cur - i, m - 1 - y);
                    for (int j = 0; j <= mj; j++) {    // 向右走j步
                        if (i == 0 && j == 0)continue;
                        // 能从(x,y)走到的点，其方案数就累加上(x,y)的方案
                        dp[x + i][y + j] = (dp[x + i][y + j] + dp[x][y]) % mod;
                    }
                }
            }
        }
        return dp[n - 1][m - 1];
    }

int main(){
    int T;
    cin>>T;
    while(T--){
        int n,m;
        cin>>n>>m;
        vector<vector<int>>energy(n, vector<int>(m));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++)
                cin>>energy[i][j];
        }
        cout<<No8_dp(energy)<<'\n';
    }
    return 0;
}