动态规划是一种解决棘手问题的方法,她将问题分解成小问题 并解决这些小问题
1 背包问题
简单算法 列出所有的组合 找到最优解
动态规划
排列顺序无关紧要
不能使用一部分
不能解决相互依赖问题
计算最终解时 不会涉及两个以上的背包
可能导致不饱和问题
计算最长公共子序列
if word_a[i]==word_b[j]:
cell[i][j]=cell[i-1][j-1]+1
else:
ceil[i][j]=max(cell[i-1][j],cell[i][j-1])
需要在给定约定的条件下优化某种指标时,动态规划很有用
问题可分解为离散子问题时,可使用动态规划解决
每种动态规划方案都设计网格
单元中的值通常就是你要优化的值
每个单元格都是一个子问题,因此需要考虑如何将问题分解为子问题
没有放四海皆准的动态规划解决方案的公式
网友评论