動的プログラミング基礎問題集 - 5つの典型問題と解法
動的プログラミング基礎問題集
=======
問題1: スキー場の最長滑走ルート
難易度: 入門～中級 解法: メモ化探索
スキー場の地図が与えられ、各地点の標高がわかっています。標高が高い地点から低い地点へのみ滑ることができるとき、最長の滑走ルートの長さを求めてください。
解法として、すべての地点を起点としてDFS（深さ優先探索）を行い、メモ化テクニックを用いて ...
8月5日 17:53 投稿
二分木の非再帰的走査
前順走査
前順走査では、ノードの値を「根 → 左の子 → 右の子」の順に処理します。
再帰的な実装
public void traverse(Node node) {
if (node == null) {
return;
}
System.out.println(node.value);
traverse(node.left);
traverse(node.right);
}
非再帰的な実装
非再帰では、スタックを使用してノードを管理します。根ノードを最初に処理 ...
8月4日 15:22 投稿
C言語で実装する階段ジャンプの問題解決手法（組合せと動的計画法）
問題の定式化
段数が n の階段を登る際、一度に1段または2段ずつ飛んで進行します。この移動規則に従い、最終段に到達するまでの全経路パターン数を計算するアルゴリズムについて解説します。
アプローチ1：数学的組合せによる求解
組合せ数学の応用では、1段ジャンプを s 回、2段ジャンプを d 回実施した場合の制約式 s + 2d = n に着目します。具体的な回数組合せが確定 ...
8月3日 23:08 投稿
最長共通部分列の解法
最長共通部分列
2つの文字列 s1 と s2 が与えられたとき、これらの文字列の最長共通部分列の長さを返してください。共通部分列が存在しない場合は 0 を返します。
文字列の部分列とは、元の文字列から文字の相対的な順序を変更せずに一部の文字を削除（または削除しない）して形成される新しい文字列です。
例えば、"ace" は "abcde" の部分列です ...
8月3日 19:44 投稿
二分探索アルゴリズムの実装と応用
二分探索は効率的な検索アルゴリズムで、ソート済み配列に対する操作に適しています。基本的な実装パターンは以下の通りです：
int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
...
8月3日 19:31 投稿
Javaプログラミングの実践的学習と課題解決
はじめに
本記事では、主に以下の重要な概念と技術について取り扱います。
クラスとオブジェクトの基本概念、コンストラクタ、アクセス修飾子、メンバ変数。
文字列入力と出力の処理方法、文字列の分割、結合、変換操作。
ループ、条件文、配列、リスト。
今回の課題は主にPTAの第7回問題セットと期末試験で構成されており、主に「成績管理システム2」と「3」、および一部 ...
8月3日 09:43 投稿
LeetCode バイウィークリーコンテスト 第111回 解説
問題2824: 目標値より小さい和を持つインデックスペアの数え上げ
この問題は、全ての可能なペアを列挙して条件を満たすものをカウントするだけで解決できます。
class Solution {
public:
int countPairs(vector<int>& values, int target) {
int length = values.size();
int result = 0;
for(int i = 0; i + 1 < length; i++) {
...
8月2日 18:56 投稿
Codeforces Round 1051 (Div. 2) A~D2問題の解説
A. 全ての長さの減算
思考問題。
長さが \(k(k \in [1,n])\) の区間を選び1を引く操作を繰り返す場合、まず\(a_i = n\) の位置を特定します。次に、\(n\) が存在する区間を維持し、\(n-k+1\) がその両側に存在するか確認し、存在すれば区間を拡張します。存在しない場合は操作は不可能です。
コードを表示```
#include <bits/stdc++.h>
using namespace std;
using i ...
8月1日 18:57 投稿
配列の探索とソートアルゴリズム
探索
1. 二分探索
前提条件：配列は事前に昇順にソートされていること
基本概念：目的値と中央要素を比較して探索範囲を半分にする
アルゴリズム手順
初期化処理：
left = 0;
right = 配列長 - 1;
pivot = left + (right - left)/2;
left <= right の間繰り返す
arr[pivot] と target を比較する
target == arr[pivot] → pivot を返却
target > arr[pivot] → le ...
8月1日 16:39 投稿
限定枚数の板による占有区間の最小被覆アルゴリズム
複数の隣接する配置ユニットが一列に連なっている状態を想定する。これらユニットのうち特定の位置には対象物が存在しており、それらの位置を最大 $M$ 枚の連続する板材で覆う必要がある。各板材は任意の長さを指定可能だが、使用できる総数は上限 $M$ に固定されている。すべての存在位置が含まれるように板材を設置した際、板材が占めるユニットの合計数を最小化するため ...
8月1日 11:28 投稿