2018面试现场年终奖金题目/记忆搜索+动态规划

题目/记忆搜索+动态规划"/>

2018面试现场年终奖金题目/记忆搜索+动态规划

面试现场/记2018/11/12## 记忆搜索+动态规划

摘自 公众号 互联网侦查
小史是一个应届生，虽然学的是电子专业，但是自己业余时间看了很多互联网与编程方面的书，一心想进BAT互联网公司。今天小史又去了一家互联网小巨头公司面试了。
随机生成矩阵 左上角走到达右下角，每次可以向右向下走，得到最大红包

例如
300 5000 6000 340 290 660
660 400 5500 330 340 8000
700 800 700 300 200 100
4000 500 3000 400 300 1000

算法的优化其实就是要避免无效计算

我用数组a[][]来表示奖金矩阵，如果到达a[1][1]，那么肯定以上面的例子来，a[0][0]->a[1][0]->a[1][1]比较好，那么底下那一条到达a[1][1]的路径就不需要了

---------------------------------------2022-5-8---------------------------------------------

/*
## 面试现场/记2018/11/12## 记忆搜索+动态规划
摘自 公众号 互联网侦查
小史是一个应届生，虽然学的是电子专业，但是自己业余时间看了很多互联网与编程方面的书，
一心想进BAT互联网公司。今天小史又去了一家互联网小巨头公司面试了。
随机生成矩阵  左上角走到达右下角，**每次可以向右向下走**，得到最大红包例如
300    5000   6000   340  290  660
660    400     5500   330  340  8000 
700    800     700     300  200    100
4000  500     3000  400  300  1000算法的优化其实就是要避免无效计算我用数组a[][]来表示奖金矩阵，如果到达a[1][1]，那么肯定以上面的例子来，
a[0][0]->a[1][0]->a[1][1]比较好，那么底下那一条到达a[1][1]的路径就不需要了
*/#include <sstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <memory>
#include <map>using namespace std;int maxValue(vector<vector<int>>& grid){int row = grid.size();int col = grid[0].size();vector<vector<int>> dp(row, vector<int>(col, 0));dp[0][0] = grid[0][0];for(int i = 0 ; i < row ; i++)for(int j = 0 ; j  < col ; j++){if(j-1>=0)dp[i][j] = dp[i][j-1] + grid[i][j];if(i-1>=0)dp[i][j] = dp[i-1][j] + grid[i][j];if(i>=1&&j>=1){dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j];}}return dp[row-1][col-1];
}    int main(){int m, n;  //随机矩阵的行和列cin >> m >> n; srand((unsigned)time(NULL)); vector<vector<int>> nums(m, vector<int>(n));for(int i = 0 ; i < m ; i++)for(int j = 0 ; j < n ; j++){nums[i][j] = rand() % 10000 + 1000;   // 随机生成 1000-10000的随机数}for(int i = 0 ; i < m ; i++){for(int j = 0; j < n ; j++){cout << nums[i][j] << " ";}cout << endl;}cout << endl;int res = maxValue(nums);cout << "res = " << res << endl;return 0;
} 

  时隔四年，翻到了这篇没有完成的博客，当时懵懵懂懂，今天一眼看穿动态规划，当时应该努力

 
 
当 i = 0 && j = 0 的时候，dp[0][0] = nums[0][0];
当 i = 0 且 j != 0 的时候 ，只有第一行，
当 j = 0 且 i != 0 的时候 ，只有第一列
当 i != 0 && j != 0 的时候，从自己的左边或者上面到达

时间复杂度 O(MN)
空间复杂度 O(1)