leetcode 困难题 1547. 切棍子的最小成本-耗时96 Minimum Cost to Cut a Stick

Problem: 1547. 切棍子的最小成本 Minimum Cost to Cut a Stick两种方案的第一种记忆化深度优先搜索第二种动态规划需要处理数组cuts加上0和n方案1: 动态规划的dp[i][j]表示cuts[i]到cuts[j]的最小成本返回dp[1][nn]递推公式是从小到大求出长度分别是2, 3, 4, …, nn-1的dp数组也就是先求出dp[1][3], dp[2][4], dp[3][5],然后求出dp[1][4], dp[2][5]…,最后求出dp[1][nn]最小长度是2[1, 2, 3]此时2可以做分割点初始化dp[i][i1] 0此时没有分割点方案2: 记忆化搜索深度优先搜索对每个可能的分割点做分割r1 dfs(cuts, left, i) dfs(cuts, i, right);求出最小值mi min(mi, r1)然后累加cuts[right] - cuts[left]; 若right - left 1则返回0记忆化mem[left][right] mi;动态规划方案 Codeclass Solution { public: int nn, sum 0; int minCost(int n, vectorint cuts) { sort( cuts.begin(), cuts.end() ); cuts.insert(cuts.begin(), 0); cuts.push_back(n); nn cuts.size(); vectorvectorint dp(nn1, vectorint(nn1, INT_MAX/10)); for(int i 1; i nn; i) dp[i][i1] 0; int mi, l, r; for(int i 2; i nn; i) { for(int j 1; j nn; j) { mi INT_MAX/10; l j; r j i; if(r nn1) continue; for(int k l 1; k r; k) { mi min(mi, dp[l][k] dp[k][r]); } mi cuts[r-1] - cuts[l-1]; dp[l][r] mi; } } return dp[1][nn]; } };方案2 记忆化深度优先搜索Codeclass Solution { public: int nn, sum 0; vectorvectorint mem; int dfs(vectorint cuts, int left, int right ) { if(right - left 1) return 0; if(mem[left][right] 0) return mem[left][right]; int r10, r2, mi INT_MAX/10; for(int i left 1; i right; i) { r1 dfs(cuts, left, i) dfs(cuts, i, right); mi min(mi, r1); } mi cuts[right] - cuts[left]; mem[left][right] mi; return mi; } int minCost(int n, vectorint cuts) { sort( cuts.begin(), cuts.end() ); cuts.insert(cuts.begin(), 0); cuts.push_back(n); nn cuts.size(); mem.assign(nn1, vectorint(nn1, -1)); int sum dfs(cuts, 0, nn-1); return sum; } };