アルゴ式(beta版)の「【特集】典型的な動的計画法のパターンを整理 ~ ナップサック DP 編 ~」二次元ナップサック DPからの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の2つで構成される、Web上で完結した学習コンテンツです。
問題 8:最長共通部分列 (LCS) 問題
/* C++による「【特集】典型的な動的計画法のパターンを整理 ~ ナップサック DP 編 ~」二次元ナップサック DPの解答例 問題 8:最長共通部分列 (LCS) 問題 https://algo-method.com/tasks/314 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ string s,t; cin>>s>>t; int ss=s.size()-0; int ts=t.size()-0; vector<vector<int>> dp(ss+1,vector<int>(ts+1,0)); for(int i=0;i<ss;i++){ for(int j=0;j<ts;j++){ if(s[i]==t[j]){ dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+1); } dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j]); dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1]); } } cout<<dp[ss][ts]<<endl; return 0; }
・問題 9:最小コスト弾性マッチング問題
/* C++による「【特集】典型的な動的計画法のパターンを整理 ~ ナップサック DP 編 ~」二次元ナップサック DPの解答例 問題 9:最小コスト弾性マッチング問題 https://algo-method.com/tasks/316 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int n,m; cin>>n>>m; vector<vector<int>> c(n,vector<int>(m)); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>c[i][j]; } } vector<vector<int>> dp(n+1,vector<int>(m+1,100000000)); dp[0][0]=0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ dp[i+1][j+1]=min({dp[i][j],dp[i+1][j],dp[i][j+1]})+c[i][j]; } } cout<<dp[n][m]<<endl; return 0; }
・問題 10:レーベンシュタイン距離 (diff コマンド)
/* C++による「【特集】典型的な動的計画法のパターンを整理 ~ ナップサック DP 編 ~」二次元ナップサック DPの解答例 問題 10:レーベンシュタイン距離 (diff コマンド) https://algo-method.com/tasks/315 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ string s,t; cin>>s>>t; int ss=s.size()-0; int ts=t.size()-0; vector<vector<int>> dp(ss+1,vector<int>(ts+1,100000000)); dp[0][0]=0; for(int i=-1;i<ss;i++){ for(int j=-1;j<ts;j++){ if(i==-1 && j==-1){ continue; } if(i>=0 && j>=0){ if(s[i]==t[j]){ dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]); }else{ dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]+1); } } if(i>=0){ dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j+1]+1); } if(j>=0){ dp[i+1][j+1]=min(dp[i+1][j+1],dp[i+1][j]+1); } } } cout<<dp[ss][ts]<<endl; return 0; }
設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式(beta版)」です。
algo-method.com