1.问题描述

给一个数组，0就是可以走，1就是有障碍，
只能往右往下走，问有几种路径走到右下角。

2.代码

//
// Created by Administrator on 2021/7/21.
//

#ifndef C__TEST01_ROADDP_HPP
#define C__TEST01_ROADDP_HPP

#include <vector>

class RoadDP {
public:
    RoadDP(vector<vector<int>> An);
    void printArray();
    int algorithmDP(vector<vector<int>> A);
    int algorithmDP2(vector<vector<int>> A);

private:
    vector<vector<int>> A;
};
RoadDP::RoadDP(vector <vector<int>> An) :
A(An)
{
    A.resize(An.size());
    for (int i = 0; i < An.size(); ++i) {
        A[i].resize(An.size());
    }
}

void RoadDP::printArray() {
    cout<<"The size of A: "<<A.size()<<endl;
    for (int i = 0; i < A.size(); ++i) {
        cout<<"The size of A["<<i<<"]: "<<A[i].size()<<endl;
    }
}

int RoadDP::algorithmDP(vector<vector<int>> A) {
    //如果是空数组
    if(A.size() == 0) return 0;

    vector<vector<int>> f;
    f.resize(A.size());
    for(int i = 0; i<A.size(); ++i){
        f[i].resize(A[i].size());
    }

    //           0                     if A[i][j] = 1
    //           1                     if A[0][0]
    // f[i][j] = f[i][j] + f[i][j-1]   if A[i][j-1] = 0
    //           f[i][j] + f[i-1][j]   if A[i-1][j] = 0
    //           f[i][j] + f[i][j-1] + f[i-1][j]    other
    for (int i = 0; i < f.size(); ++i) {
        for (int j = 0; j < f[i].size(); ++j) {
            if(i == 0 && j==0){
                f[0][0] = 1; //Initialization
                continue;
            }
            f[i][j] = 0;
            if(A[i][j] == 1)   f[i][j] = 0;
            else{
                if(j-1 >= 0) f[i][j] += f[i][j-1];
                if(i-1 >= 0) f[i][j] += f[i-1][j];
            }
        }
    }
    return f[f.size()-1][f[0].size()-1];
}

int RoadDP::algorithmDP2(vector<vector<int>> A) {
    //如果是空数组
    if(A.size() == 0) return 0;

    vector<vector<int>> f;
    f.resize(A.size());
    for(int i = 0; i<A.size(); ++i){
        f[i].resize(A[i].size());
    }

    f[0][0] = 1;//Initialization

    for (int i = 0; i < f.size(); ++i) {
        f[i][0] = 1;
        if(A[i][0] == 1){
            for (int j = i; j < f.size(); ++j) {
                f[j][0] = 0;
            }
            break;
        }
    }

    for (int i = 0; i < f[0].size(); ++i) {
        f[0][i] = 1;
        if(A[0][i] == 1){
            for (int j = i; j < f[0].size(); ++j) {
                f[0][j] = 0;
            }
            break;
        }
    }
    //           0                     if A[i][j] = 1
    //           1                     if A[0][0]
    // f[i][j] = f[i][j] + f[i][j-1]   if A[i][j-1] = 0
    //           f[i][j] + f[i-1][j]   if A[i-1][j] = 0
    //           f[i][j] + f[i][j-1] + f[i-1][j]    other
    for (int i = 1; i < f.size(); ++i) {
        for (int j = 1; j < f[i].size(); ++j) {
            f[i][j] = 0;
            if(A[i][j] == 1)   f[i][j] = 0;
            else{
                 f[i][j] += f[i][j-1];
                 f[i][j] += f[i-1][j];
            }
        }
    }
    return f[f.size()-1][f[0].size()-1];
}
#endif //C__TEST01_ROADDP_HPP

两种方法求解。

验证：

#include <iostream>
using namespace std;
#include "RoadDP.hpp"
//动态规划问题：
//给一个数组，0就是可以走，1就是有障碍，
// 只能往右往下走，问有几种路径走到右下角

int main() {
    vector<vector<int>> An = {
            {0, 1, 0},
            {0, 1, 0},
            {0, 0, 0}
    };
    RoadDP rdp(An);
    rdp.printArray();
    //int result = rdp.algorithmDp(An);
    int result = rdp.algorithmDP2(An);

    cout<<result<<endl;

    return 0;
}