Scribd Logo
Upload

Welcome to Scribd!

  • 3 views

    dynamic programming

    Uploaded by

    Karthik Nadar

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    dynamic programming

    Uploaded by

    Karthik Nadar
    3 views4 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    3 views4 pages

    dynamic programming

    Uploaded by

    Karthik Nadar

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 4

    1.

    Fibonacci Sequence (Using Dynamic Programming)

    The Fibonacci sequence is a great way to demonstrate dynamic programming. It has overlapping
    subproblems, and solving each subproblem once can significantly improve efficiency.

    Fibonacci Using Memoization (Top-Down Approach)

    #include <stdio.h>

    // Define the maximum number of Fibonacci numbers


    #define MAX 100

    // Array to store the computed Fibonacci numbers


    int memo[MAX];

    // Function to calculate Fibonacci using memoization


    int fib_memo(int n) {
    if (n <= 1)
    return n;

    if (memo[n] != -1) // If the result is already computed, return it


    return memo[n];

    // Otherwise, calculate and store the result


    memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
    return memo[n];
    }

    int main() {
    // Initialize the memoization array to -1 (indicating uncomputed values)
    for (int i = 0; i < MAX; i++) {
    memo[i] = -1;
    }

    int n = 10; // Example Fibonacci number to calculate


    printf("Fibonacci number %d is %d\n", n, fib_memo(n));

    return 0;
    }

    Explanation:

     memo[] array is used to store the results of previously calculated Fibonacci numbers.
     Each Fibonacci number is computed only once and reused when needed, making the time
    complexity O(n)O(n)O(n) instead of O(2n)O(2^n)O(2n).

    Time Complexity: O(n)O(n)O(n)


    Space Complexity: O(n)O(n)O(n)

    Fibonacci Using Tabulation (Bottom-Up Approach)

    c
    #include <stdio.h>

    int fib_tab(int n) {
    if (n <= 1) return n;

    int table[n + 1]; // Array to store the Fibonacci values


    table[0] = 0;
    table[1] = 1;

    // Build the table iteratively


    for (int i = 2; i <= n; i++) {
    table[i] = table[i - 1] + table[i - 2];
    }

    return table[n];
    }

    int main() {
    int n = 10; // Example Fibonacci number to calculate
    printf("Fibonacci number %d is %d\n", n, fib_tab(n));

    return 0;
    }

    Explanation:

     A bottom-up approach builds the solution from the smallest subproblems (starting from
    fib(0) and fib(1)) up to the desired Fibonacci number.
     The solution uses an iterative approach to fill the table[] array.

    Time Complexity: O(n)O(n)O(n)


    Space Complexity: O(n)O(n)O(n)

    2. 0/1 Knapsack Problem (Dynamic Programming)

    The 0/1 Knapsack problem is a classic problem where you need to maximize the total value of
    items that can fit into a knapsack with a limited capacity.

    0/1 Knapsack Problem Using Tabulation

    #include <stdio.h>

    int knapsack(int weights[], int values[], int W, int n) {


    int dp[n + 1][W + 1]; // DP table to store the maximum value at each
    subproblem

    // Build the table in a bottom-up manner


    for (int i = 0; i <= n; i++) {
    for (int w = 0; w <= W; w++) {
    if (i == 0 || w == 0) {
    dp[i][w] = 0; // Base case: No items or no capacity means 0
    value
    } else if (weights[i - 1] <= w) {
    // Include the item or exclude it
    dp[i][w] = (values[i - 1] + dp[i - 1][w - weights[i - 1]] >
    dp[i - 1][w]) ?
    (values[i - 1] + dp[i - 1][w - weights[i - 1]]) :
    dp[i - 1][w];
    } else {
    dp[i][w] = dp[i - 1][w]; // Item can't be included, so just
    carry over the previous result
    }
    }
    }

    return dp[n][W]; // The maximum value achievable with n items and


    capacity W
    }

    int main() {
    int weights[] = {2, 3, 4, 5}; // Weights of the items
    int values[] = {3, 4, 5, 6}; // Values of the items
    int W = 5; // Capacity of the knapsack
    int n = sizeof(weights) / sizeof(weights[0]);

    printf("Maximum value in knapsack = %d\n", knapsack(weights, values, W,


    n));

    return 0;
    }

    Explanation:

     A 2D dp array is used where dp[i][w] represents the maximum value obtainable using
    the first i items with a knapsack capacity of w.
     We iteratively fill the table based on whether to include or exclude an item.

    Time Complexity: O(nW)O(nW)O(nW)


    Space Complexity: O(nW)O(nW)O(nW)

    0/1 Knapsack Problem Using Space Optimization (1D Array)

    #include <stdio.h>

    int knapsack_optimized(int weights[], int values[], int W, int n) {


    int dp[W + 1]; // 1D array for optimized space complexity

    // Initialize the dp array


    for (int i = 0; i <= W; i++) {
    dp[i] = 0;
    }

    // Build the dp array in a bottom-up manner


    for (int i = 0; i < n; i++) {
    for (int w = W; w >= weights[i]; w--) {
    dp[w] = (values[i] + dp[w - weights[i]] > dp[w]) ?
    (values[i] + dp[w - weights[i]]) : dp[w];
    }
    }

    return dp[W]; // Maximum value that can be obtained with capacity W


    }

    int main() {
    int weights[] = {2, 3, 4, 5}; // Weights of the items
    int values[] = {3, 4, 5, 6}; // Values of the items
    int W = 5; // Capacity of the knapsack
    int n = sizeof(weights) / sizeof(weights[0]);

    printf("Maximum value in knapsack = %d\n", knapsack_optimized(weights,


    values, W, n));

    return 0;
    }

    Explanation:

     Instead of using a 2D array, we use a 1D array dp[] where dp[w] stores the maximum
    value achievable with capacity w.
     We iterate from W down to the weight of the current item to avoid overwriting values that
    haven't been computed yet for smaller capacities.

    Time Complexity: O(nW)O(nW)O(nW)


    Space Complexity: O(W)O(W)O(W)

    Conclusion:

    Both Fibonacci and Knapsack problems demonstrate dynamic programming principles in C:

     Memoization (Top-Down) stores intermediate results to avoid redundant calculations


    and ensures efficiency.
     Tabulation (Bottom-Up) builds solutions iteratively, often with a 2D table (or optimized
    to 1D for space efficiency).

    Dynamic programming optimizes the time complexity by solving each subproblem only once,
    leading to significant improvements in performance for problems with overlapping subproblems.

    You might also like