王争老师动态规划讲得确实精彩，就是课后练习没有答案，有时候解不出来会很难受。我是看了下一篇文章的讲解然后明白了这篇文章的课后习题解法，这里分享一下吧，希望对大家有帮助。

int[][] matrix = {{5},{7,8},{2,3,4},{4,9,6,1},{2,7,9,4,5}};

public int yanghuiTriangle(int[][] matrix) {
    int[][] state = new int[matrix.length][matrix.length];
    state[0][0] = matrix[0][0];
    for (int i = 1; i < matrix.length; i++) {
        for (int j = 0; j < matrix[i].length; j++) {
            if (j == 0) state[i][j] = state[i - 1][j] + matrix[i][j];
            else if (j == matrix[i].length - 1) state[i][j] = state[i - 1][j - 1] + matrix[i][j];
            else {
                int top1 = state[i - 1][j - 1];
                int top2 = state[i - 1][j];
                state[i][j] = Math.min(top1, top2) + matrix[i][j];
            }
        }
    }
    int minDis = Integer.MAX_VALUE;
    for (int i = 0; i < matrix[matrix.length - 1].length; i++) {
        int distance = state[matrix.length - 1][i];
        if (distance < minDis) minDis = distance;
    }
    return minDis;
}

关于knapsack2函数
1 states表示当前背包总重量所有可能取值的集合
2 如果将第i个物品放入背包，我们需要在当前背包总重量的所有取值中，找到小于等于j的（j=w-items[i]）
3 为什么第6行j需要从大到小来处理？因为循环的目的是在当前背包总重量的所有可能取值中，找到小于等于j的，如果j从小到大来处理，states[j+items[i]] = true;这个赋值会影响后续的处理
public static int knapsack2(int[] items, int n, int w) {
  boolean[] states = new boolean[w+1]; // 默认值 false
  states[0] = true; // 第一行的数据要特殊处理，可以利用哨兵优化
  states[items[0]] = true;
  for (int i = 1; i < n; ++i) { // 动态规划
    for (int j = w-items[i]; j >= 0; --j) {// 把第 i 个物品放入背包
      if (states[j]==true) states[j+items[i]] = true;
    }
  }
  for (int i = w; i >= 0; --i) { // 输出结果
    if (states[i] == true) return i;
  }
  return 0;
}

这个动态规划学习了三天了，把老师的代码都手练了一遍，感觉对动态规划有点感觉了！然后在写这个课后题，我也练了一遍，我练了这么多，但我觉得动态规则这个最重要的是每层可达的状态这个怎么计算的，这是重点，我开始的时候，用纸和笔，把老师的第一例子，中的状态都画了出来，然后再来看代码，感觉很有帮助！

杨晖三角的代码我我也贴出来，希望对其他童鞋有帮助，老师，也麻烦你帮忙看下，看我的实现是否存在问题，谢谢！

由于这个限制，限制长度，没有贴出来倒推出路径，可查看我的git
https://github.com/kkzfl22/datastruct/blob/master/src/main/java/com/liujun/datastruct/algorithm/dynamicProgramming/triangle/Triangle.java


int[][] status = new int[triangles.length][triangles[triangles.length - 1].length];

    int startPoint = triangles.length - 1;
    int maxpoint = triangles[triangles.length - 1].length;

    // 初始化相关的数据
    for (int i = 0; i <= startPoint; i++) {
      for (int j = 0; j < maxpoint; j++) {
        status[i][j] = -1;
      }
    }

    // 初始化杨晖三解的第一个顶点
    status[0][startPoint] = triangles[0][startPoint];

    // 开始求解第二个三角形顶点
    // 按层级遍历
    for (int i = 1; i <= startPoint; i++) {
      // 加入当前的位置节点
      int currIndex = 0;
      while (currIndex < maxpoint) {
        if (status[i - 1][currIndex] > 0) {
          // 计算左节点
          int leftValue = status[i - 1][currIndex] + triangles[i][currIndex - 1];

          // 1,检查当前左节点是否已经设置，如果没有，则直接设置
          if (status[i][currIndex - 1] == -1) {
            status[i][currIndex - 1] = leftValue;
          } else {
            if (leftValue < status[i][currIndex - 1]) {
              status[i][currIndex - 1] = leftValue;
            }
          }
          // 计算右节点
          int rightValue = status[i - 1][currIndex] + triangles[i][currIndex + 1];

          if (status[i][currIndex + 1] == -1) {
            status[i][currIndex + 1] = rightValue;
          }
          currIndex++;
        }
        currIndex++;
      }
    }

    int minValue = Integer.MAX_VALUE;
    for (int i = 0; i < maxpoint; i++) {
      if (minValue > status[startPoint][i] && status[startPoint][i] != -1) {
        minValue = status[startPoint][i];
      }
    }
    System.out.println("最短路径结果为:" + minValue);

记录一下自己的 swift 版本一维数组动态规划装东西
/*
 *
 * 动态规划
 
 * 注意 Source 里面应该是 public, 运行时才不好报错
 **/
public struct DynamicProgramming {
    init() {
    }
    
    public static func knapsack2(_ items: Array<Int>, _ maxWeight: Int ) -> Void {
        let count = items.count
        var states = Array<Bool>.init(repeating: false, count: count + 1)
        // 首个没有放入
        states[0] = true
        // 首个放入了
        states[items[0]] = true
        for i in 1..<count { // 动态规划
            // 从去除已经计算过重量的最大的重量开始算起i, 把第 i 个物品放入背包
            for j in 0 ... (maxWeight - items[i]) {// 除了第 i 个物品, 剩余重量,如果有计算过的, 那么再加上第 i 个物品, 记录此时总重量的状态
                if (states[j] == true) {
                    let total = j + items[i]
                    states[total] = true
                }
            }
        }
        for v in (0 ... maxWeight).reversed() {
            if states[v] {
                print("maxWeight index: \(v)")
                break
            }
        }
    }
}

老师，这是我基于理解动态规划之后写出的优化版斐波那契数列，是否算是动态规划入门了 - -
function faibonacci(n) {
    //可以基于动态规划的思想去优化
    //存储每一个步骤的值，然后推导出之后的值
    let hash = {};
    const calcu = (n) => {
        if (n === 1 || n === 2) return 1;
        let a = hash[n - 1] || calcu(n - 1);
        let b = hash[n - 2] || calcu(n - 2);
        return a + b;
    }
    for (let i = 1; i <= n; i++) {
        hash[i] = calcu(i)
    }
    return hash[n]
}