动态规划的定义
将原问题拆解成若干子问题 ,同时保存子问题的答案,使得每个子问题只求解一次,最终获得原问题的答案。
动态规划的一般流程
例子1:一维空间的动态规划
题目:求斐波那契数列
int fibonacci(int i) {
return i <= 1 : i : fibonacci(i - 1) + fibonacci(i - 2);
}
暴力递归的时间复杂度是指数级,我们需要使用记忆化搜索去解决这个问题
int fibonacci(int fib) {
int[] cache = new int[fib + 1];
for (int i = 0; i < cache.length; i++) {
if (fib <= 1) {
cache[i] = i;
continue;
}
cache[i] = cache[i - 2] + cache[i - 1];
}
return cache[fib];
}
复杂的动态规划
复杂的动态规划:
- 维度变化了 有可能是二维或三维空间;
- 中间可能会有取舍最优子结构
题目2:不同路径
题目描述:一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
对于上述问题,由于每次只能 向右或向下 走,于是我们可以转变为子问题:
子问题1:对于A如何走到右下角
子问题2:对于B如何走到右下角
所以总共的走法就等于 【A】的子问题的解+【B】的子问题的解
int paths(int m, int n) {
int[][] table = new int[m][n];
return dfs(table, 0, 0);
}
int dfs(int[][] table, int row, int col) {
if (row < 0 || row >= table.length || col < 0 || col >= table[0].length) {
return 0;
}
if (row == table.length - 1 && col == table[0].length - 1) {
return 1;
}
return dfs(table, row + 1, col) + dfs(table, row, col + 1);
}
int paths(int m, int n) {
int[][] table = new table[m][n];
for (int i = 0; i < m; i++) {
table[m][0] = 1;
}
for (int i = 0; i < n; i++) {
table[0][n] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
table[i][j] = table[i - 1][j] + table[i][j - 1];
}
}
return table[m - 1][n - 1];
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)