内容整合自[动态编程模式][1] 同时加上自己的一些总结

模型

大部分动态规划可以归结为以下五种模型来解决：

  1. 最小/最大路径 ： 给定目标，找到达到目标的最小（最大）成本/路径/总和。

  2. 统计方法总数 ： 给定目标，统计有多少种方法到达目标

  3. 合并间隔 ： 给定一组数字，考虑到当前数字以及从左侧和右侧可获得的最佳数值，找到解决问题的最佳方案。

  4. 决策问题 ： 给定一组值，找到答案，并提供选择或忽略当前值的选项。

  5. 字符串 ： 回文字符串，最长子序列等问题。

最小/最大路径

方法

在当前状态之前的所有可能路径中选择最小（最大）路径，然后为当前状态添加权重值。

routes[i] = min(routes[i-1], routes[i-2], ... , routes[i-k]) + cost[i]

为目标中的所有值生成最佳解决方案，然后返回目标的值。

模板代码

for (int i = 1; i <= target; ++i) {
   for (int j = 0; j < ways.size(); ++j) {
       if (ways[j] <= i) {
           dp[i] = min(dp[i], dp[i - ways[j]]) + cost / path / sum;
       }
   }
} 
return dp[target]

LeetCode 上的相关问题

746.最低价攀登楼梯 Easy

for (int i = 2; i <= n; ++i) {
   dp[i] = min(dp[i-1], dp[i-2]) + (i == n ? 0 : cost[i]);
}

 
return dp[n]

64.最小路径总和 Medium

for (int i = 1; i < n; ++i) {
   for (int j = 1; j < m; ++j) {
       grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j];
   }
}
 
return grid[n-1][m-1]

322.硬币找零 Medium

for (int j = 1; j <= amount; ++j) {
   for (int i = 0; i < coins.size(); ++i) {
       if (coins[i] <= j) {
           dp[j] = min(dp[j], dp[j - coins[i]] + 1);
       }
   }
}

931.最小下降路径总和 Medium

983.最低票价 Medium

650.2键键盘 Medium

279.完美正方形 Medium

1049.最后一块石头的重量II Medium

120.三角形 Medium

474.一和零 Medium

221.最大广场 Medium

322.硬币找零 Medium

1240.用最小的正方形平铺一个矩形 Hard

174.地下城游戏 Hard

871.最小加油站数 Hard

统计方法总数

方法

记录从0 -> n 的所有情况并进行累加
routes[i] = routes[i-1] + routes[i-2]+ … + routes[i-k]

模板

for (int i = 1; i <= target; ++i) {
   for (int j = 0; j < ways.size(); ++j) {
       if (ways[j] <= i) {
           dp[i] += dp[i - ways[j]];
       }
   }
}
 
return dp[target]

LeetCode 上的相关问题

类似问题
70.爬楼梯 easy

for (int stair = 2; stair <= n; ++stair) {
for (int step = 1; step <= 2; ++step) {
dp[stair] += dp[stair-step];
}
}
62.独特的道路 Medium

for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
dp[i][j] = dp[i][j-1] + dp[i-1][j];
}
}
1155.目标总数的骰子卷数 Medium

for (int rep = 1; rep <= d; ++rep) {
vector new_ways(target+1);
for (int already = 0; already <= target; ++already) {
for (int pipe = 1; pipe <= f; ++pipe) {
if (already - pipe >= 0) {
new_ways[already] += ways[already - pipe];
new_ways[already] %= mod;
}
}
}
ways = new_ways;
} //这题真的尼玛难；
PS : 注意一些问题指出了重复的次数，在这种情况下，还要增加一个循环来模拟每个重复。

688.国际象棋骑士的概率 Medium

494.目标总和 Medium

377.组合和IV Medium

935.骑士拨号器 Medium

1223.骰子滚动模拟 Medium

416.分区相等子集总和 Medium

808.汤服务 Medium

  1. Domino和Tromino平铺 Medium

801.使序列增加的最小掉期

673.最长递增子序列数 Medium

63.独特之路II Medium

576.超越界限 Medium

1269.经过一些步骤后留在同一个地方的方式数量 Hard

1220.元音排列 Hard

合并间隔

决策问题

字符串

[1]: https://leetcode.com/discuss/general-discussion/458695/dynamic-programming-patterns# Minimum-(Maximum)-Path-to-Reach-a-Target