[DP]01背包和三角形最小路径和

站点挂了，回档到四月，补档。

01背包

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int N,V;
	cin>>N>>V;
	int w[N],c[N];
	for(int i=0;i<N;i++){
		cin>>w[i];
	}
	for(int i=0;i<N;i++){
		cin>>c[i];
	}
	int dp[V]={0};
	for(int i=1;i<=N;i++){
		for(int v=V;v>=w[i];v--){
			dp[v]=max(dp[v],dp[v-w[i]])+c[i];
		}
	}
	int max = 0;
	for(int v=0;v<V;v++){
		if(dp[v]>max){
			max=p[v];
		}
	}
	cout<<max<<endl;
}

三角形最小路径和（LeetCode No.120）

从最底层向上处理，把最后两层合并为一层，一直向上到根节点。

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int length = triangle.size();
        int[] ns = new int[length];
        if(length==1){return triangle.get(0).get(0);}
        for(int i=0;i<length;i++){
            ns[i]=triangle.get(length-1).get(i);
        }
        for(int i=length-2;i>=0;i--){
            for(int j=0;j<=i;j++){
                ns[j]=Math.min(ns[j],ns[j+1])+triangle.get(i).get(j);
            }
        }
        return ns[0];
    }
}