寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

アルゴ式(beta版): C++による「動的計画法」2 次元の動的計画法の解答例

アルゴ式(beta版)の「動的計画法」2 次元の動的計画法からの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の2つで構成される、Web上で完結した学習コンテンツです。

C++による「動的計画法」2 次元の動的計画法の解答例

僕が作成、提出したコードは、以下のとおりです。

Q2-1. 表と数字 (1)

algo-method.com

/*
C++による「動的計画法」2 次元の動的計画法の解答例
Q2-1. 表と数字 (1)
https://algo-method.com/tasks/324
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    vector<vector<int>> a(4,vector<int>(4,0));
    for(int i=0;i<4;i++){
        cin>>a[0][i];
    }
    for(int i=0;i<3;i++){
        for(int j=0;j<4;j++){
            a[i+1][j]+=a[i][j];
            if(j-1>=0){
                a[i+1][j-1]+=a[i][j];
            }
            if(j+1<4){
                a[i+1][j+1]+=a[i][j];
            }
        }
    }
    cout<<a[3][3]<<endl;
    return 0;
}
・Q2-2. 表と数字 (2)

algo-method.com

/*
C++による「動的計画法」2 次元の動的計画法の解答例
Q2-2. 表と数字 (2)
https://algo-method.com/tasks/325
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin>>n;
    vector<vector<int>> a(n,vector<int>(n,0));
    for(int i=0;i<n;i++){
        cin>>a[0][i];
    }
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n;j++){
            a[i+1][j]+=a[i][j];
            a[i+1][j]%=100;
            if(j-1>=0){
                a[i+1][j-1]+=a[i][j];
                a[i+1][j-1]%=100;
            }
            if(j+1<n){
                a[i+1][j+1]+=a[i][j];
                a[i+1][j+1]%=100;
            }
        }
    }
    cout<<a[n-1][n-1]<<endl;
    return 0;
}
・Q2-3. 3 つの仕事

algo-method.com

/*
C++による「動的計画法」2 次元の動的計画法の解答例
Q2-3. 3 つの仕事
https://algo-method.com/tasks/41
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin>>n;
    vector<vector<int>> a(n,vector<int>(3));
    for(int i=0;i<n;i++){
        for(int j=0;j<3;j++){
            cin>>a[i][j];
        }
    }
    vector<vector<int>> dp(n,vector<int>(3,0));
    for(int i=0;i<3;i++){
        dp[0][i]=a[0][i];
    }
    for(int i=0;i<n-1;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                if(j==k){
                    continue;
                }
                dp[i+1][k]=max(dp[i+1][k],dp[i][j]+a[i+1][k]);
            }
        }
    }
    cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]))<<endl;
    return 0;
}
・Q2-4. コマの移動 (1)

algo-method.com

/*
C++による「動的計画法」2 次元の動的計画法の解答例
Q2-4. コマの移動 (1)
https://algo-method.com/tasks/329
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin>>n;
    vector<vector<int>> dp(n,vector<int>(n,0));
    dp[0][0]=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i+1<n){
                dp[i+1][j]+=dp[i][j];
            }
            if(j+1<n){
                dp[i][j+1]+=dp[i][j];
            }
        }
    }
    cout<<dp[n-1][n-1]<<endl;
    return 0;
}
・Q2-5. コマの移動 (2)

algo-method.com

/*
C++による「動的計画法」2 次元の動的計画法の解答例
Q2-5. コマの移動 (2)
https://algo-method.com/tasks/333
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin>>n;
    vector<string> s(n);
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    vector<vector<int>> dp(n,vector<int>(n,0));
    dp[0][0]=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i+1<n && s[i+1][j]=='.'){
                dp[i+1][j]+=dp[i][j];
            }
            if(j+1<n && s[i][j+1]=='.'){
                dp[i][j+1]+=dp[i][j];
            }
        }
    }
    cout<<dp[n-1][n-1]<<endl;
    return 0;
}
・Q2-6. コマの移動 (3)

algo-method.com

/*
C++による「動的計画法」2 次元の動的計画法の解答例
Q2-6. コマの移動 (3)
https://algo-method.com/tasks/334
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin>>n;
    vector<vector<int>> a(n,vector<int>(n));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>a[i][j];
        }
    }
    vector<vector<int>> dp(n,vector<int>(n));
    dp[0][0]=a[0][0];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i+1<n){
                dp[i+1][j]=max(dp[i+1][j],dp[i][j]+a[i+1][j]);
            }
            if(j+1<n){
                dp[i][j+1]=max(dp[i][j+1],dp[i][j]+a[i][j+1]);
            }
        }
    }
    cout<<dp[n-1][n-1]<<endl;
    return 0;
}
・Q2-7. コマの移動 (4)

algo-method.com

/*
C++による「動的計画法」2 次元の動的計画法の解答例
Q2-7. コマの移動 (4)
https://algo-method.com/tasks/335
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin>>n;
    vector<vector<int>> a(n,vector<int>(n));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>a[i][j];
        }
    }
    vector<vector<int>> dp(n,vector<int>(n,100000000));
    dp[0][n-1]=a[0][n-1];
    for(int i=0;i<n;i++){
        for(int j=n-1;j>=0;j--){
            if(i+1<n){
                dp[i+1][j]=min(dp[i+1][j],dp[i][j]+a[i+1][j]);
            }
            if(j-1>=0){
                dp[i][j-1]=min(dp[i][j-1],dp[i][j]+a[i][j-1]);
            }
        }
    }
    cout<<dp[n-1][0]<<endl;
    return 0;
}

設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式(beta版)」です。
algo-method.com