API tools faq
paste
Advertisement
Fastrail08

Minimum Falling Path Sum

Fastrail08
Jun 16th, 2025
52
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.13 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void getMinFallingSum(int row, int col, int sum, int &minSum, vector<vector<int> > &v){
  5.     if(row >= v.size()){
  6.         if(col < 0 || col >= v[0].size()){
  7.             minSum = min(minSum, sum);
  8.         }
  9.         return;
  10.     }
  11.     if(col < 0 || col >= v[0].size()){
  12.         return;
  13.     }
  14.     //levels - each cell
  15.     //options - bottom left, bottom, bottom right
  16.     sum += v[row][col];
  17.     getMinFallingSum(row + 1, col - 1, sum, minSum, v);
  18.     getMinFallingSum(row + 1, col, sum, minSum, v);
  19.     getMinFallingSum(row + 1, col + 1, sum, minSum, v);
  20. }
  21.  
  22. int getMinFallingSumMemo(int row, int col, vector<vector<int> > &v, vector<vector<int> > &memo){
  23.     if(row == v.size() - 1 && (col >= 0 && col < v[0].size())){
  24.         return v[row][col];
  25.     }
  26.     if(memo[row][col] != INT_MAX){
  27.         return memo[row][col];
  28.     }
  29.     int bottomLeft = INT_MAX, bottom = INT_MAX, bottomRight = INT_MAX;
  30.     if(row < v.size() - 1 && col > 0){
  31.         bottomLeft = getMinFallingSumMemo(row + 1, col - 1, v, memo);
  32.     }
  33.    
  34.     if(row < v.size() - 1){
  35.         bottom = getMinFallingSumMemo(row + 1, col, v, memo);
  36.     }
  37.    
  38.     if(row < v.size() - 1 && col < v[0].size() - 1){
  39.         bottomRight = getMinFallingSumMemo(row + 1, col + 1, v, memo);
  40.     }
  41.    
  42.    
  43.     return memo[row][col] = v[row][col] + min(bottomLeft, min(bottom, bottomRight));
  44.    
  45. }
  46.  
  47. int getMinFallingSumDP(vector<vector<int> > &v){
  48.     int n = v.size(), m = v[0].size();
  49.     vector<vector<int> > dp(n, vector<int>(m, INT_MAX));
  50.    
  51.     for(int j = 0; j < m; j++){
  52.         dp[n - 1][j] = v[n - 1][j];
  53.     }
  54.     int minFallingSum = INT_MAX;
  55.     for(int i = n - 2; i >= 0; i--){
  56.         for(int j = 0; j < m; j++){
  57.             int bottomLeft = 0, bottom = 0, bottomRight = 0;
  58.             if(j == 0){
  59.                 dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]);
  60.             }
  61.             else if(j == m - 1){
  62.                 dp[i][j] = min(dp[i + 1][j - 1], dp[i + 1][j]);
  63.             }
  64.             else{
  65.                 dp[i][j] = min(dp[i + 1][j - 1], min(dp[i + 1][j], dp[i + 1][j + 1]));
  66.             }
  67.             dp[i][j] += v[i][j];
  68.             if(i == 0){
  69.                 minFallingSum = min(minFallingSum, dp[i][j]);
  70.             }
  71.         }
  72.     }
  73.     return minFallingSum;
  74. }
  75.  
  76. int main() {
  77.     // your code goes here
  78.     int n, m;
  79.     cin >> n >> m;
  80.     vector<vector<int> > v(n, vector<int>(m));
  81.     for(int i = 0; i < n; i++){
  82.         for(int j = 0; j < m; j++){
  83.             cin >> v[i][j];
  84.         }
  85.     }
  86.     /*
  87.         //Recursive Call
  88.        
  89.         int minSum = INT_MAX;
  90.         for(int j = 0; j < m; j++){
  91.             getMinFallingSum(0, j, 0, minSum, v);
  92.         }
  93.         cout << minSum << '\n';
  94.     */
  95.    
  96.    
  97.    
  98.     /*
  99.         //Memo Call
  100.         int minSum = INT_MAX;
  101.         vector<vector<int> > memo(n, vector<int>(m , INT_MAX));
  102.         for(int j = 0; j < m; j++){
  103.             minSum = min(minSum, getMinFallingSumMemo(0, j, v, memo));
  104.         }
  105.         cout << minSum << '\n';
  106.     */
  107.    
  108.    
  109.     //DP Call
  110.     cout << getMinFallingSumDP(v) << '\n';
  111.    
  112. }
  113.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!