階段登拝における最小コストの算出

配列の各要素が階段のコストを表しており、索引 i の階段を登る際に cost[i] の体力を消費します。支払い済みの場合、1 つまたは 2 つの階段を 건너갈 수 있습니다. 最上部に到達するための最小総コストを求めます。初期位置として索引 0 または 1 を選択可能です。

状態遷移としては、i 番目の階段に到達する最小コストは、i-1 番目からの移動コストと i-2 番目からの移動コストの小さい方になります。

int calculateMinCost(int* expenses, int len) {
    int *memo = (int *)calloc(len + 1, sizeof(int));
    // 初期位置のコストは 0 とみなす
    memo[0] = 0;
    memo[1] = 0;
    
    for (int k = 2; k <= len; k++) {
        int fromPrev = memo[k - 1] + expenses[k - 1];
        int fromPrevPrev = memo[k - 2] + expenses[k - 2];
        memo[k] = (fromPrev < fromPrevPrev) ? fromPrev : fromPrevPrev;
    }
    int result = memo[len];
    free(memo);
    return result;
}

連続する期間の最大売上高

整数配列 sales に每日の売上データが格納されています。連続する 1 日以上の期間において、売上合計が最大となる値を返す必要があります。時間計算量は O(n) で実装します。

これは最大部分和問題であり、累積和が負になった場合はリセットする手法（Kadane's Algorithm）を適用します。

int findMaxRevenue(int* data, int size) {
    if (size == 0) return 0;
    int globalMax = data[0];
    int currentSum = 0;
    
    for (int i = 0; i < size; i++) {
        currentSum += data[i];
        if (currentSum > globalMax) {
            globalMax = currentSum;
        }
        if (currentSum < 0) {
            currentSum = 0;
        }
    }
    return globalMax;
}

配列ジャンプの最小ステップ数

0 索引の整数配列 nums が与えられます。nums[i] は位置 i から前方へジャンプできる最大距離を示します。配列の末尾まで到達するために必要な最小ジャンプ回数を計算します。

各位置 i に対して、そこに到達可能な以前の位置 j から的最小ステップ数を更新していく動的計画法を用います。

int minJumpsToEnd(int* steps, int arrSize) {
    int *minSteps = (int *)malloc(sizeof(int) * arrSize);
    for (int i = 0; i < arrSize; i++) minSteps[i] = INT_MAX;
    
    minSteps[0] = 0;
    
    for (int i = 1; i < arrSize; i++) {
        for (int j = 0; j < i; j++) {
            if (j + steps[j] >= i) {
                int candidate = minSteps[j] + 1;
                if (candidate < minSteps[i]) {
                    minSteps[i] = candidate;
                }
            }
        }
    }
    int res = minSteps[arrSize - 1];
    free(minSteps);
    return res;
}

最長連続増加部分列の長さ

未排序の整数配列から、連続して増加している部分列の最大長を見つけます。ここでいう連続とは、配列内の索引が連続していることを意味します。

動的計画法というよりは、単走査でカウンタを管理するだけで解決可能です。

int getLCISLength(int* arr, int n) {
    if (n == 0) return 0;
    int maxLen = 1;
    int currentStreak = 1;
    
    for (int i = 1; i < n; i++) {
        if (arr[i - 1] < arr[i]) {
            currentStreak++;
        } else {
            currentStreak = 1;
        }
        if (currentStreak > maxLen) {
            maxLen = currentStreak;
        }
    }
    return maxLen;
}

最長増加部分列（LIS）

整数配列 nums から、厳密に増加する部分列の最大長を求めます。部分列は配列から要素を削除して得られる序列であり、連続である必要はありません。

dp[i] を「索引 i を終端とする最長増加部分列の長さ」と定義し、それ以前の要素と比較して更新します。

int computeLIS(int* sequence, int size) {
    if (size == 0) return 0;
    int *dpTable = (int *)malloc(sizeof(int) * size);
    int overallMax = 1;
    dpTable[0] = 1;
    
    for (int i = 1; i < size; i++) {
        dpTable[i] = 1;
        for (int j = 0; j < i; j++) {
            if (sequence[j] < sequence[i]) {
                int newLen = dpTable[j] + 1;
                if (newLen > dpTable[i]) {
                    dpTable[i] = newLen;
                }
            }
        }
        if (dpTable[i] > overallMax) {
            overallMax = dpTable[i];
        }
    }
    free(dpTable);
    return overallMax;
}

最長増加部分列の個数

最長増加部分列の長さに加え、そのような部分列が何通り存在するかを返します。厳密な増加序列である必要があります。

長さだけでなく、その長度を達成するパスの数を記録する配列を併せて管理します。

int countLISPaths(int* nums, int n) {
    if (n == 0) return 0;
    int *lengths = (int *)malloc(sizeof(int) * n);
    int *ways = (int *)malloc(sizeof(int) * n);
    int maxLen = 0;
    int totalCount = 0;
    
    for (int i = 0; i < n; i++) {
        lengths[i] = 1;
        ways[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                if (lengths[j] + 1 > lengths[i]) {
                    lengths[i] = lengths[j] + 1;
                    ways[i] = ways[j];
                } else if (lengths[j] + 1 == lengths[i]) {
                    ways[i] += ways[j];
                }
            }
        }
        
        if (lengths[i] > maxLen) {
            maxLen = lengths[i];
            totalCount = ways[i];
        } else if (lengths[i] == maxLen) {
            totalCount += ways[i];
        }
    }
    free(lengths);
    free(ways);
    return totalCount;
}

最長共通部分配列

二つの整数配列 nums1 と nums2 が与えられたとき、両方に共通する部分配列のうち最も長いものの長さを返します。部分配列は連続している必要があります。

二次元の DP テーブルを用い、一致する要素があれば対角線方向の値に 1 を加算します。

int findMaxCommonSubarray(int* seqA, int sizeA, int* seqB, int sizeB) {
    int **matrix = (int **)malloc((sizeA + 1) * sizeof(int *));
    for (int i = 0; i <= sizeA; i++) {
        matrix[i] = (int *)calloc(sizeB + 1, sizeof(int));
    }
    
    int result = 0;
    for (int i = 1; i <= sizeA; i++) {
        for (int j = 1; j <= sizeB; j++) {
            if (seqA[i - 1] == seqB[j - 1]) {
                matrix[i][j] = matrix[i - 1][j - 1] + 1;
                if (matrix[i][j] > result) {
                    result = matrix[i][j];
                }
            }
        }
    }
    
    for (int i = 0; i <= sizeA; i++) free(matrix[i]);
    free(matrix);
    return result;
}