本文主要是介绍Hot100-动态规划,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
动态规划与贪心的区别:
动态规划是由前一个状态推导出来的(时序),
而贪心是局部直接选最优的
动态规划问题解题五步曲:
- 确定dp数组(dp table)以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
118. 杨辉三角 - 力扣(LeetCode)
class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> dp = new LinkedList<>();//递推初始化,初始化第一行List<Integer> firstrow = new LinkedList<>();firstrow.add(1);dp.add(firstrow);for(int i = 1; i < numRows; i++){List<Integer> row = new LinkedList<>();for(int j = 0; j <= i; j++){if(j==0 || j==i){row.add(1);}else{//dp[i][j] = dp[i-1][j-1] + dp[i-1][j];row.add(dp.get(i-1).get(j-1)+dp.get(i-1).get(j));}}// 在内部循环结束后,应该将生成的行加入到 dp 中dp.add(row);}return dp;}
}
这篇关于Hot100-动态规划的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!