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