【基础算法】动态规划

public class FibonacciDP {
    public static int fibonacci(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

1. 背包问题
   • 0 - 1 背包问题描述：有一个容量为  的背包和  个物品，每个物品有重量  和价值 。每个物品要么放入背包，要么不放入背包，要求在不超过背包容量的情况下，选择物品使得背包内物品的总价值最大。
   • 代码实现（以 Java 为例）：

   • public class Knapsack {
         public static int knapsack(int C, int[] w, int[] v, int n) {
             int[][] dp = new int[n + 1][C + 1];
             for (int i = 1; i <= n; i++) {
                 for (int j = 0; j <= C; j++) {
                     if (w[i - 1] <= j) {
                         dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
                     } else {
                         dp[i][j] = dp[i - 1][j];
                     }
                 }
             }
             return dp[n][C];
         }
     }