アルゴ式（beta版）: C++による「動的計画法」動的計画法ってなに？の解答例

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

C++による「動的計画法」動的計画法ってなに？の解答例

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

Q1-1. 数字の列

algo-method.com

/*
C++による「整数論的アルゴリズム (beta)」約数の解答例
Q1-1. 数字の列
https://algo-method.com/tasks/302
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n,x,y;
    cin>>n>>x>>y;
    vector<int> a(n,0);
    a[0]=x;
    a[1]=y;
    for(int i=2;i<n;i++){
        a[i]=(a[i-2]+a[i-1])%100;
    }
    cout<<a[n-1]<<endl;
    return 0;
}

・Q1-2. マスの移動 (1)

algo-method.com

/*
C++による「動的計画法」動的計画法ってなに？の解答例
Q1-2. マスの移動 (1)
https://algo-method.com/tasks/303
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    vector<int> t(n);
    t[0]=0;
    t[1]=a[1];
    for(int i=2;i<n;i++){
        t[i]=min(t[i-1]+a[i],t[i-2]+a[i]*2);
    }
    cout<<t[n-1]<<endl;
    return 0;
}

・Q1-3. 階段ののぼり方

algo-method.com

/*
C++による「動的計画法」動的計画法ってなに？の解答例
Q1-3. 階段ののぼり方
https://algo-method.com/tasks/304
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin>>n;
    vector<int> v(n+1);
    v[0]=1;
    v[1]=1;
    for(int i=2;i<=n;i++){
        v[i]=v[i-2]+v[i-1];
    }
    cout<<v[n]<<endl;
    return 0;
}

・Q1-4. タイルの敷き詰め

algo-method.com

/*
C++による「動的計画法」動的計画法ってなに？の解答例
Q1-4. タイルの敷き詰め
https://algo-method.com/tasks/305
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin>>n;
    vector<int> v(n+1,0);
    v[0]=1;
    for(int i=1;i<=n;i++){
        if(i>=1){
            v[i]+=v[i-1];
        }
        if(i>=2){
            v[i]+=v[i-2];
        }
        if(i>=3){
            v[i]+=v[i-3];
        }
    }
    cout<<v[n]<<endl;
    return 0;
}

・Q1-5. マスの移動 (2)

algo-method.com

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

・Q1-6. すごろく

algo-method.com

/*
C++による「動的計画法」動的計画法ってなに？の解答例
Q1-6. すごろく
https://algo-method.com/tasks/323
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n,m;
    cin>>n>>m;
    vector<int> d(m);
    for(int i=0;i<m;i++){
        cin>>d[i];
    }
    vector<bool> dp(n+1,false);
    dp[0]=true;
    for(int i=1;i<=n;i++){
        for(int j=0;j<m;j++){
            if(i-d[j]>=0 && dp[i-d[j]]==true){
                dp[i]=true;
            }
        }
    }
    if(dp[n]){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}

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