동적 계획 - 지정된 값으로 결합

개요:
leetcode를 갱신하고 두 개의 동적 기획 문제를 만났습니다. 각각 코인 change II, target sum입니다.이 두 문제는 같은 제목에 속한다. 즉, 제공된 한 조의 숫자에 따라 지정된 숫자를 조합하면coinchange II의 숫자는 중복될 수 있고 targetsum의 숫자는 중복될 수 없다. 이런 차이로 인해 그들은 동적 계획을 할 때 다르다.coin change II 방향은 아래에서 위로, target sum은 위에서 아래로.
제목:coin change II
You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.
Note: You can assume that

0 <= amount <= 5000

1 <= coin <= 5000

the number of coins is less than 500

the answer is guaranteed to fit into signed 32-bit integer

Example 1:

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

Input: amount = 10, coins = [10] 
Output: 1

class Solution {
public:
    int change(int amount, vector& coins) {
        
        int len=coins.size();   //          ，len=0,amount=0,        1，  0  
        vector dp(amount+1,0);
        
        dp[0]=1;
        
        for(int i=0;i

제목: target sum
You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and - . For each integer, you should choose one from + and - as its new symbol.
Find out how many ways to assign symbols to make sum of integers equal to target S.
Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.

Note:

The length of the given array is positive and will not exceed 20.

The sum of elements in the given array will not exceed 1000.

Your output answer is guaranteed to be fitted in a 32-bit integer.

class Solution {
public:
    int findTargetSumWays(vector& nums, int S) {
        //          
        int len=nums.size();
        if(len==0) return 0;
        
        int sum=0;
        int target;
        for(int i=0;i dp(target+1,0);
        dp[0]=1;
        for(int i=0;i=nums[i];j--)
            //for(int j=num[i];j<=target;j++)
            {
                dp[j]+=dp[(j-nums[i])];
            }
        }
        return dp[target];
    }
};

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

CodeForces 140 E. New Year Garland(콤보 수학+dp)

Description n열, i열 li 위치, 현재 모든 위치에 m가지 색깔로 색칠을 하려면 만족해야 합니다. 1. 한 줄씩 서로 인접한 위치마다 다른 색 2. 인접 배열에 사용되는 색상 세트가 다름 질문 시나리오 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

동적 계획 - 지정된 값으로 결합

좋은 웹페이지 즐겨찾기