MiserMan_DP

//I think the first DP question whose answer I've thought out completely in Iterative method lmao

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,m;
    cin>>n>>m;
    int ** arr = new int*[n];
    for(int i=0;i<n;i++){
        arr[i] = new int[m];
        for(int j=0;j<m;j++){
            cin>>arr[i][j];
        }
    }
    int ** dp = new int*[n];//Cities
    for(int i=0;i<n;i++){
        dp[i] = new int[m];//Bus choice at each city
    }
    for(int i=0;i<m;i++){
        dp[n-1][i]=arr[n-1][i];
    }
    for(int i=n-2;i>=0;i--){
        for(int j=0;j<m;j++){
            if(j==0){
                dp[i][j]=arr[i][j]+min(dp[i+1][j],dp[i+1][j+1]);
            }
            else if(j==m-1){
                dp[i][j]=arr[i][j]+min(dp[i+1][j],dp[i+1][j-1]);
            }
            else{
                dp[i][j]=arr[i][j]+min(dp[i+1][j-1],min(dp[i+1][j],dp[i+1][j+1]));
            }
        }
    }
    int ans = dp[0][0];
    for(int i=1;i<m;i++){
        if(dp[0][i]<ans){
            ans = dp[0][i];
        }
    }
    cout<<ans<<endl;
    return 0;
}